[ BOJ ][JAVA][16927] 배열 돌리기 2

www.acmicpc.net/problem/16927

16927번: 배열 돌리기 2

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	1321	431	354	36.086%

문제

크기가 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의 원소 Aij가 주어진다.

출력

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

제한

• 2 ≤ N, M ≤ 300
• 1 ≤ R ≤ 109
• min(N, M) mod 2 = 0
• 1 ≤ Aij ≤ 108

예제 입력 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

코드

/*
    배열돌리기2
    p16926(배열돌리기1) 과 다른점은 요구하는 반복 횟수 r이 커짐에 따라 불필요한 회전이 있으므로
    시간을 더 단축하여 효율적인 코드를 작성해야 한다.
    따라서 각 테두리 변의 크기에 따라 반복 횟수를 수정하여 불필요한 회전 수를 줄인다.
*/

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

public class p16927 {
    static int N, M, R;
    // 시계반대방향으로 전진해야 하므로 dr, dc의 인덱스는 오 아 왼 위 순서
    static int[] dr = {0, 1, 0, -1};
    static int[] dc = {1, 0, -1, 0};
    static int[][] map;
    public static void main(String[] args) 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());

        map = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 박스 (테두리)의 개수
        int cnt = Math.min(N, M) / 2;

        int n = N, m = M;

        // 반복문 돌 때마다 박스 1개가 r만큼 전진한다.
        for (int i = 0; i < cnt; i++) {
            rotate(i, 2*n + 2*m - 4);
            // 박스 안으로 들어갈 때마다 가로, 세로 2씩 줄어든다.
            n -= 2;
            m -= 2;
        }

        print();
    }

    static void rotate(int start, int len) {
        // len은 박스의 총 칸수.
        int rr = R % len;
        for (int i = 0; i < rr; i++) { // rr칸 전진

            int startVal = map[start][start];
            int r = start;
            int c = start;
            int dir = 0;

            while (dir < 4) {
                // map[nr][nc] 는 옮길 대상이다. (-> map[r][c]의 위치로!!)
                int nr = r + dr[dir];
                int nc = c + dc[dir];

                if (nr == start && nc == start) break;
                if (nr < N - start && nc < M - start && nr >= start && nc >= start) {
                    // 차례대로 시계 반대방향으로 옮긴다.
                    map[r][c] = map[nr][nc];
                    r = nr;
                    c = nc;
                } else {
                    // 다음에 옮길 칸이 배열 밖으로 넘어가버리면 해당 라인은 다 옮긴 것이므로 다음 라인으로 넘어간다
                    dir++;
                }
            }
            // 처음에 시작지점 빼놨던 것은 마지막 빈자리에 넣어준다.
            map[start + 1][start] = startVal;
        }
    }

    static void print() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                sb.append(map[i][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }
}