백준 알고리즘 - 17276 배열 돌리기

www.acmicpc.net/problem/17276

17276번: 배열 돌리기

 

시뮬레이션 문제의 대표격인 '배열 돌리기' 시리즈입니다.

 

백준 알고리즘에 '배열 돌리기'라는 이름으로 검색하면 시리즈가 1~7 외에도 몇개 더 있는데

그 중에 아예 번호가 붙어있지 않은 문제를 풀어보았습니다.

 

 

문제를 분석해보자면 홀수 N개의 행과 열을 가진 배열을 십자와 대각선에 해당하는 부분들만 골라서 시계방향 또는 반시계방향으로 45도의 배수만큼 돌리는 문제입니다.

 

저는 마치 시계를 돌리는 것과 같다는 생각이 들어 N/2, N/2로 중심이 되는 index를 구한 후,

해당 index로 부터 8방향 탐색을 하듯 dx, dy를 더해가며 해당하는 element들만 골라서 queue에 저장하였습니다.

 

그리고 queue에서 offer와 poll을 반복하며 회전을 대체하여 다시 알맞는 자리에 element들을 넣어주는 방식으로 회전을 구현하였습니다.

 

예를 들면,

 

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20
21	22	23	24	25

 

여기서 중앙에 해당하는 index는 {5/2, 5/2} = {2, 2}의 13입니다.

처음으로 queue에 들어가는 건 {7, 8, 9, 14, 19, 24, 23, 22, 17} 이렇게 되겠군요.

그 뒤, 만일 반시계방향으로 45도 돌리고 싶다면 queue의 맨 앞에 있는 7을 poll해서 다시 맨 뒤로 offer해주면 됩니다.

그러면 queue의 상태가 {8, 9, 14, 19, 24, 23, 22, 17, 7} 이렇게 되겠네요.

 

그 뒤에 다시 자리에 차례대로 넣어주면

 

1	2	3	4	5
6	8	9	14	10
11	7	13	19	15
16	12	17	18	20
21	22	23	24	25

 

이렇게 안쪽이 반시계방향으로 45도 회전한 배열이 완성됩니다.

 

이 과정을 가장 바깥쪽 부분이 회전할 때까지 반복하면 배열 1개를 완전히 회전시킬 수 있게 됩니다.

 

 

이와 같은 과정을 테스트케이스 갯수만큼 반복하는 것으로 이 문제는 해결할 수 있습니다.

 

 

아래는 전체 코드입니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_배열돌리기_17276 {
								
	private static int[] dx = {-1, -1, -1, 0, 1, 1, 1, 0};
	private static int[] dy = {-1, 0, 1, 1, 1, 0, -1, -1}; 
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();
		
		// T : 테스트케이스 갯수
		int T = Integer.parseInt(br.readLine());
		
		// 테스트케이스만큼 반복
		for(int i = 0; i < T; i++) {
			StringTokenizer tk = new StringTokenizer(br.readLine(), " ");
			// N : arr의 크기
			int N = Integer.parseInt(tk.nextToken());
			// degree : 회전 각도를 45로 나누어 받는다.
			int degree = Integer.parseInt(tk.nextToken()) / 45;
			
			// arr : 입력받을 arr
			int[][] arr = new int[N][N];
			
			// arr입력
			for(int j = 0; j < N; j++) {
				tk = new StringTokenizer(br.readLine(), " ");
				for(int k = 0; k < N; k++) {
					arr[j][k] = Integer.parseInt(tk.nextToken());
				}
			}
			
			// x, y : 중심으로 돌아가게 되는 좌표.
			int x = N/2;
			int y = N/2;
			
			// 입력받은 degree에 따라 arr 회전.
			// N/2만큼 for문을 돌면서 안쪽에서 부터 돌려나감.
			for(int j = 1; j <= N/2; j++) {
				Queue<Integer> que = new ArrayDeque<Integer>();
				
				// 위에서 선언한 index array를 이용해 상좌, 상, 상우, 우, 하우, 하, 하좌, 좌 순으로 queue에 삽입
				for(int k = 0; k < 8; k++) {
					que.offer(arr[x + dx[k] * j][y + dy[k] * j]);
				}
				
				// 반시계 방향의 경우
				if(degree < 0) {
					// 해당 각에 맞추어 queue의 맨 앞에서 꺼낸 뒤 맨 뒤에 넣음으로써 회전을 대체
					// 단, 45도를 8번 받으면 360도로 의미가 없어지므로 %8을 통해 무의미한 회전을 줄임.
					for(int k = 0; k < (-degree)%8; k++) {
						que.offer(que.poll());
					}
					
					// 다시 arr에 elements 삽입.
					for(int k = 0; k < 8; k++) {
						arr[x + dx[k] * j][y + dy[k] * j] = que.poll();
					}
				}else {	// 시계 방향의 경우
					// 해당 각에 맞추어 queue의 맨 앞에서 꺼낸 뒤 맨 뒤에 넣음으로써 회전을 대체
					// 단, 45도를 8번 받으면 360도로 의미가 없어지므로 %8을 통해 무의미한 회전을 줄임.
					for(int k = 0; k < 8 - degree%8; k++) {
						que.offer(que.poll());
					}
					
					// 다시 arr에 elements 삽입.
					for(int k = 0; k < 8; k++) {
						arr[x + dx[k] * j][y + dy[k] * j] = que.poll();
					}
				}
			}
			
			// 출력.
			for(int j = 0; j < N; j++) {
				for(int k = 0; k < N; k++) {
					sb.append(arr[j][k]).append(" ");
				}sb.append("\n");
			}
		}
		
		System.out.println(sb.toString());

	}

}