[알고리즘] 백준16926 배열돌리기1 - 자바

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

16926번: 배열 돌리기 1

 

 

[재귀 풀이 코드]

package day0211;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_16926_배열돌리기 {
	static int N, M, R, tmp, idx, depth;
	static int[] dy = {1, 0, -1, 0};
	static int[] dx = {0, 1, 0, -1};
	static int[][] graph;
	static boolean[][] visited; 
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		
		graph = new int[N][M];
		
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				graph[i][j] = Integer.parseInt(st.nextToken());
			}
		} // 배열 담기
		
		
		for(int r=0; r<R; r++) {//회전시작
			visited = new boolean[N][M];
		
			for(int i=0; i< Math.min(N, M)/2; i++){
				tmp = graph[depth][depth];
				dfs(depth, depth);
				idx = 0; // 하 우 상 좌
				depth++;
			}
			depth = 0;
			
		}// 회전종료
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				System.out.print(graph[i][j] + " ");
			}
			System.out.println();
		}// 배열출력
		
	}
	static void dfs(int y, int x) {
		int pre = tmp; // 이전 값 저장
		
		while(idx<4) {
			int yy = y + dy[idx];
			int xx = x + dx[idx];
			
			if(yy>=0 && yy<N && xx>=0 && xx<M && !visited[yy][xx]) {
				tmp = graph[yy][xx];
				graph[yy][xx] = pre;
				visited[yy][xx] = true;
				dfs(yy, xx);
			}else {//만약, 범위내통과x 방문체크x
				idx++;
			}
		}
		
	}
}

풀이 흔적

 

• 그래프만 보면 BFS만 애용했기에.. 큰 맘먹고 DFS로 도전해보았지만 그냥 반복문으로 해결할 수 있는 문제라는 것..
  
  
• tmp, idx, depth변수는 순서대로 tmp는 이전 배열의 값을 담는 목적, idx는 델타 배열인 dy, dx의 인덱스를 위해 설정했다. 재귀로 했기에 범위가 벗어나면 idx를 +1 해준다. 여기서 dy, dx 배열은 순서가 무조건 반시계 방향인 하, 우, 상, 좌 순으로 선언해야 한다.
• 재귀를 들어가기 전 회전이 시작되는 for문에서는 Math.min(N, M)/2를 통해 회전이 배열 안에서 총 몇 번 도는지 구했다. 처음에는 이중 for문을 써서 방문을 하지 않은 경우 돌게끔 해서 수정을 했지만 속도 차이는 크게 차이가 없었다.
  
  
• dfs함수는 이전 값을 저장하는 것과 범위가 벗어나면 idx++ 해주는 부분이 핵심인 것 같다.

 

[반복문 풀이 코드]

package day0211;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_16927_배열돌리기2 {
	static int N, M, R;
//	static int[] dy = {0, 1, 0, -1}; // 우하좌상
//	static int[] dx = {1, 0, -1, 0};
	
	static int[] dy = {1, 0, -1, 0}; // 하우상좌
	static int[] dx = {0, 1, 0, -1};
	static int[][] graph;
	static boolean[][] visited;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());

		graph = new int[N][M];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				graph[i][j] = Integer.parseInt(st.nextToken());
			}
		} // 배열 담기

		for (int r = 0; r < R; r++) {// 회전시작
			for (int j = 0; j < Math.min(N, M) / 2; j++) {// 사각형 내에서 몇번을 돌지
				int y = j;
				int x = j;

				int idx = 0;
				int pre = graph[y][x];
				int tmp = 0;
				while (idx < 4) {
					int yy = y + dy[idx];
					int xx = x + dx[idx];
					if (yy >= j && yy < N - j && xx >= j && xx < M - j) {
						tmp = graph[yy][xx];
						graph[yy][xx] = pre;
						pre = tmp;
						y = yy;
						x = xx;
					} else
						idx++;
				}
				
			}
		} // 회전종료

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				System.out.print(graph[i][j] + " ");
			}
			System.out.println();
		} // 배열출력

	}
}

 

[성능 차이]

1540ms가 나온건 반복문 2184ms가 나온건 재귀다. 속도차이는 꽤?? 나는건가 모르겠다. 아직 볼 줄 몰라서.. 그래도 메모리나 속도적인 부분은 반복문이 훨씬 수치가 적게 나왔다.