배열돌리기2[백준 16927][실버3][Java]

 

[광고 누르면 오늘의 행운 상승!!]

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

16927번: 배열 돌리기 2

실버 아닌거같다.

너무 어려웠다ㅠ ㅠ

배열을 그냥 돌리면 시간초과가 난다. 4번 돌리기 = 0번 돌리기 와 같으므로 

나머지 연산을 사용하여 몇번 돌릴지를 정해주었다. 또한 바깥쪽 배열과 안쪽 배열의

회전수도 달라야 하므로 각각 돌리기 횟수를 구해서 DFS 돌려버렸다.

import java.util.*;
import java.io.*;

public class Main {
	public static final int[] dx = {1,0,-1,0};
	public static final int[] dy = {0,1,0,-1};
	
	public static int intVisit[][];
	public static int map[][];
	public static int N,M, time;
	public static int before, after, depth, dir =0;
	
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		time = sc.nextInt();
		map = new int[N][M];
		intVisit = new int[N][M];
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				map[i][j] = sc.nextInt();
				intVisit[i][j] = -1;
			}
		}
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(intVisit[i][j] >= 0) continue;
				
				int num = ((N-1-(depth*2))*2) +((M-1-(depth*2))*2); //4x4 기준 12회 반복하면 한바퀴를 돈다.
				if(time%num != 0) num = time%num;
				                                                                                        
				
				for (int k = 0; k < num; k++) {
					before = map[i][j];
					dir = 0;
					dfs(i,j);
				}
				depth++;
			}
		}
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				System.out.print(map[i][j]+ " ");
			}
			System.out.println();
		}
		
	}
	
	public static void dfs(int row, int col) {
		
		if(intVisit[row][col] == -1) intVisit[row][col] = depth;
		
		int nx = row + dx[dir];
		int ny = col + dy[dir];
		
		if(nx < 0 || nx >= N || ny < 0 || ny >= M) {
			dir++;
			if(dir > 3) return;
			
			nx = row + dx[dir];
			ny = col + dy[dir];
			
		}else if(intVisit[nx][ny] != depth && intVisit[nx][ny] != -1) {
			//자신의 깊이가 아니면서 방문하지 않은곳도 아닐때 (남의 깊이)
			dir++;
			if(dir > 3) return;
			
			nx = row + dx[dir];
			ny = col + dy[dir];
		}
	
		after  = map[nx][ny];
		map[nx][ny] = before;
		before = after;
		
		dfs(nx,ny);
	}
}