[백준] 16927번 - 배열 돌리기 2 (Gold 5)

문제 링크

백준 16927번 - 배열 돌리기 2 (Gold 5)

문제 설명

크기가 N x M인 배열이 주어져 있을 때, 배열을 반시계 방향으로 R번 회전 시킨 결과를 출력한다.
배열을 반시계 방향으로 한 번 회전시키면 아래와 같이 회전이 일어난다.

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]

정답 코드 및 설명

배열의 가장 바깥에 해당하는 부분부터 한 껍질씩 회전을 시키면 된다.

위 그림에서 빨간색이 가장 바깥 껍질, 연두색이 안쪽 껍질에 해당한다.
N x M 크기의 배열에서 총 껍질의 개수는 $\textrm{min}(N / 2, M / 2)$임은 쉽게 알 수 있다.
각 껍질을 한 칸씩 회전시키는 과정은 네 변을 나누어서 구현하면 된다.
비슷한 테크닉을 백준 17144번 - 미세먼지 안녕! 문제에서도 활용하였다.

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

public class BOJ16927 {
    int n, m, r;
    int[][] arr;

    void input() throws IOException {
        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());
        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());
            }
        }
    }

    void rotate(int j) {
        int total = 2 * n + 2 * m - 4 - 8 * j;
        ArrayList<int[]> curr = new ArrayList<>(total);
        for (int i = j; i < m - j; i++) {
            curr.add(new int[]{j, i, arr[j][i]});
        }
        for (int i = j + 1; i < n - 1 - j; i++) {
            curr.add(new int[]{i, m - 1 - j, arr[i][m - 1 - j]});
        }
        for (int i = m - j - 1; i >= j; i--) {
            curr.add(new int[]{n - 1 - j, i, arr[n - 1 - j][i]});
        }
        for (int i = n - 2 - j; i > j; i--) {
            curr.add(new int[]{i, j, arr[i][j]});
        }
        for (int i = 0; i < total; i++) {
            arr[curr.get(i)[0]][curr.get(i)[1]] = curr.get((i + r) % total)[2];
        }
    }

    void solution() throws IOException {
        input();
        for (int i = 0; i < n / 2 && i < m / 2; i++) {
            rotate(i);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                sb.append(arr[i][j]).append(' ');
            }
            sb.append('\n');
        }
        System.out.println(sb);
    }

    public static void main(String[] args) throws IOException {
        new BOJ16927().solution();
    }
}