[백준, BOJ 16926] 배열 돌리기 1 (java)

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

16926번: 배열 돌리기 1

---

문제

크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다.

A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5]
   ↓                                       ↑
A[2][1]   A[2][2] ← A[2][3] ← A[2][4]   A[2][5]
   ↓         ↓                   ↑         ↑
A[3][1]   A[3][2] → A[3][3] → A[3][4]   A[3][5]
   ↓                                       ↑
A[4][1] → A[4][2] → A[4][3] → A[4][4] → A[4][5]

예를 들어, 아래와 같은 배열을 2번 회전시키면 다음과 같이 변하게 된다.

1 2 3 4       2 3 4 8       3 4 8 6
5 6 7 8       1 7 7 6       2 7 8 2
9 8 7 6   →   5 6 8 2   →   1 7 6 3
5 4 3 2       9 5 4 3       5 9 5 4
 <시작>         <회전1>        <회전2>

배열과 정수 R이 주어졌을 때, 배열을 R번 회전시킨 결과를 구해보자.

입력

첫째 줄에 배열의 크기 N, M과 수행해야 하는 회전의 수 R이 주어진다.

둘째 줄부터 N개의 줄에 배열 A의 원소 $A_{ij}$가 주어진다.

출력

입력으로 주어진 배열을 R번 회전시킨 결과를 출력한다.

제한

• 2 ≤ N, M ≤ 300
• 1 ≤ R ≤ 1,000
• min(N, M) mod 2 = 0
• 1 ≤ $A_{ij}$ ≤ $10^8$

728x90

 

예제 입력 1

4 4 2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

예제 출력 1

3 4 8 12
2 11 10 16
1 7 6 15
5 9 13 14

 

예제 입력 2

5 4 7
1 2 3 4
7 8 9 10
13 14 15 16
19 20 21 22
25 26 27 28

예제 출력 2

28 27 26 25
22 9 15 19
16 8 21 13
10 14 20 7
4 3 2 1

 

예제 입력 3

2 2 3
1 1
1 1

예제 출력 3

1 1
1 1

---

 

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

public class Main {

	public static void main(String[] args) throws Exception{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		// N, M, R 입력
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int R = Integer.parseInt(st.nextToken());
		
		// N x M 크기의 배열 선언 & 입력
		int[][] arr = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		// 한 겹 씩 큐에 넣기
		LinkedList<Queue<Integer>> qList = new LinkedList<>(); // 큐를 넣은 리스트
		
		int[] dx = {0, 1, 0, -1};
		int[] dy = {1, 0, -1, 0};
		
		int x = 0;
		int y = -1;
		int d = 0;
		int count = 0;
		
		while(count < N * M) {
			if(d == 0) {
				qList.add(new LinkedList<>());
			}
			
			int nx = x + dx[d];
			int ny = y + dy[d];
			
			Queue<Integer> tmpQ = qList.get(qList.size() - 1);
			
			while(nx >= 0 && nx < N && ny >= 0 && ny < M && arr[nx][ny] != 0) {
				tmpQ.add(arr[nx][ny]);
				arr[nx][ny] = 0;
				x = nx;
				y = ny;
				nx = x + dx[d];
				ny = y + dy[d];
				count++;
			}
			d = (d + 1) % 4;
		}
		
		// 큐에 넣은 수 R만큼 poll & add
		for (int i = 0; i < qList.size(); i++) {
			Queue<Integer> tmpQ = qList.get(i);
			
			for (int j = 0; j < R; j++) {
				tmpQ.add(tmpQ.poll());
			}
		}
		
		// 다시 배열에 넣어주기
		x = 0;
		y = -1;
		d = 0;
		count = 0;
		int qIdx = -1;
		Queue<Integer> tmpQ = null;
		while(count < N * M) {
			if(d == 0) {
				tmpQ = qList.get(++qIdx);
			}
			
			int nx = x + dx[d];
			int ny = y + dy[d];
			
			
			while(nx >= 0 && nx < N && ny >= 0 && ny < M && arr[nx][ny] == 0) {
				arr[nx][ny] = tmpQ.poll();
				x = nx;
				y = ny;
				nx = x + dx[d];
				ny = y + dy[d];
				count++;
			}
			d = (d + 1) % 4;
		}
		
		// 출력
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				sb.append(arr[i][j]);
				if(j == M - 1) sb.append("\n");
				else sb.append(" ");
			}
		}
		System.out.println(sb);
	}

}