16926번: 배열돌리기1

https://www.acmicpc.net/problem/16926

16926번: 배열 돌리기 1

제한조건 : min(N,M)%2==0 -> 가로,세로가 짝수가 보장됨-> 아래,오,위,왼 못돌리는 경우 안들어옴

규칙발견 : min(N,M)/2 == 로테이션할 횟수

 

* swap 구현 방법1

temp1=이전값

temp2=현재값

현재값=temp1

temp1=temp2

...

 

 

* 의사코드

dr,dc=아래,오,위,왼

dfs{

- 종료조건

if(depth==돌려야되는횟수==가로,세로중작은거/2)

return

 

while{

if(배열아웃 or 이미방문한곳)->마지막좌측순서임->break

                                              ->아님->방향전환,continue

선입선출->큐로 swap구현

}

q클리어

다음원소로(대각선아래로) dfs = > 내부회전

 

 

Main{

for(r번만큼){

dfs

check배열 초기화

}

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main_16926_유동훈 {

	static int n;
	static int m;
	static int r;
	static int[] dr= {1,0,-1,0};
	static int[] dc= {0,1,0,-1};
	static int cur;
	static int[][] map;
	static boolean[][] check;
	static Queue<Integer> q= new LinkedList<>();


	static void dfs(int r,int c, int depth)
	{
		//if(depth==Math.min(n, m)%2) return;
		if(depth==Math.min(n, m)/2) 
			{
				//print();
				return;
			}
		
		int origin_r=r;
		int origin_c=c;
		//int cur=0;
		int nr;
		int nc;
		cur=0;
		//int temp=0;
		//boolean start=true;
		while(true)
		{
			nr=r+dr[cur%4];
			nc=c+dc[cur%4];
			if(nr<0 || nr>=n || nc<0 || nc>=m || check[nr][nc]==true)
			{
				
				if(dc[cur%4]==-1 && dr[cur%4]==0)	//순환끝내는 조건 
				{
					break;
				}
				cur++;	//방향전환
				continue;
			}
			
			if(q.isEmpty())
				q.add(map[r][c]);
			q.add(map[nr][nc]);
			map[nr][nc]=q.poll();
			check[nr][nc]=true;
			
        	r=nr;
        	c=nc;
        	
        	
        	
        	//nr=r+dr[cur%4];
        	//nc=r+dc[cur%4];
        }
		q.clear();
		//print();
		dfs(origin_r+1,origin_c+1,depth+1);
		
		
	}
	
	static void print()
	{
		StringBuilder sb=new StringBuilder();
		 for(int i=0;i<n;++i)
	        {
	        	for(int j=0;j<m;++j)
	        	{
	        		sb.append(map[i][j]+" ");
	        	}
	        	sb.append("\n");
	        }
		 System.out.println(sb);
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //int n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        n=Integer.parseInt(st.nextToken());
        m=Integer.parseInt(st.nextToken());
        r=Integer.parseInt(st.nextToken());
        
        map=new int[n][m];
        check=new boolean[n][m];
        for(int i=0;i<n;++i)
        {
        	st = new StringTokenizer(br.readLine());
        	for(int j=0;j<m;++j)
        	{
        		map[i][j]=Integer.parseInt(st.nextToken());
        	}
        }
        
        for(int k=0;k<r;++k)
        {
        	dfs(0,0,0);
            for(int i=0;i<n;++i)
            {
            	//st = new StringTokenizer(br.readLine());
            	for(int j=0;j<m;++j)
            	{
            		check[i][j]=false;
            	}
            }
            //dfs(0,0,0);
        }
        
        //dfs(1,1,1);
        print();
        //dfs(0,0,0);
        //dfs(1,1,2);
        //print();
        

	}

}