[백준/Java] 17470 배열 돌리기 5

🔗 문제 링크: https://www.acmicpc.net/problem/17470

 

🔍 해결 과정

배열 돌리기 3 문제와 내용은 같으나 연산의 수 R의 최댓값이 200만이라는 점에서 차이가 있습니다.

직접 배열의 내용 자체를 가지고 연산을 활용하기에는 시간복잡도 O(NMR)을 가지기 때문에 최악의 경우 200만 x 10000 = 200억의 연산이 진행이 되기에 일반적인 풀이로는 시간초과가 발생합니다. 그래서 처음에는 배열의 내용들을 바탕으로 연산하기보다는 배열의 영역을 매핑하여 압축시키고 이를 바탕으로 연산을 진행해야겠다는 생각을 했습니다. 즉 그림으로 표현하자면 다음과 같습니다.

 

배열을 4개의 영역으로 매핑

 

위 네 가지의 영역을 바탕으로 2 x 2 압축된 배열을 만들고 R번 연산을 진행을 하게 된다면 최대 2 X 2 X 200만 = 800만의 연산을 진행하게 되어 시간 초과 문제를 해결할 수가 있습니다.

 

하지만 또 하나 처리해야할 문제가 있는데 압축된 배열을 바탕으로 연산을 진행하다보면 압축된 배열의 내용들도 같이 변경이 된다는 점입니다. 예를 들어서 다음과 같은 배열을 좌우 반전하면 그림과 같이 압축된 내용들도 같이 좌우 반전이 된다는 것을 볼 수가 있습니다.

그림과 같이 영역 뿐만 아니라 압축 내용들도 같이 좌우 반전이 되는 것을 볼 수가 있다.

 

그래서 이 압축된 내용들의 변경들도 어떻게 처리를 해주어야 할지 여기에서 고민이 좀 많았던 문제였습니다.

 

결론적으로는 좌우반전, 상하반전, 회전 관련 전역 변수를 활용하여 연산 후 최종 변경한 내용들을 반영함으로써 문제를 해결했습니다.

코드에 있는 boolean 형태의 colFlip(좌우 반전), rowFlip(상하 반전)과 int 형태의 turn(오른쪽으로 90도 회전) 변수를 말합니다.

 

turn 변수 같은 경우는 오른쪽으로 90도 회전을 기준으로 했는데 이는 4번 돌릴 때 배열들이 같아 지는 현상을 이용하였습니다.

예를 들면 왼쪽으로 한번 회전한 경우는 오른쪽으로 3번 회전한 경우랑 같은 경우와 같습니다.

 

문제는 turn과 반전을 혼용하는 경우인데 turn을 홀수 번 진행했는지 안했는지의 여부에 따라서 colFlip(좌우 반전), rowFlip(상하 반전)의 활용 경우가 달라집니다.

예를 들어서 그림과 같이 오른쪽으로 90도 한 번 회전한 상태에서 좌우 반전한 내용들은 상하 반전을 진행하고 오른쪽으로 90도 회전하는 경우와 같습니다.

이 원리를 활용하여 그림에서 첫 번째의 연산의 순서(오른쪽 90도 회전 후 좌우 반전)가 적용이 되었다고 가정한다면 turn 변수에는 1(오른쪽 한 번 회전했다는 얘기가 된다)이 적용이 되었으므로 행과 열이 뒤바뀐 상태가 됩니다. 행과 열이 반전이 된 상태이기 때문에 좌우 반전 시 colFlip 변수가 아닌 rowFlip 변수를 true로 설정을 진행해줌으로써 상태를 저장해줍니다. 그렇게 연산을 통해서 변수들에 최종 내용들이 반영이 되었을텐데 최종적으로 살펴볼 때는 상하 또는 좌우 반전 여부를 먼저 살펴준 다음에 turn 수만큼 오른쪽 90도 회전을 진행합니다. 즉, 그림에서 두 번째 부분에 속합니다.

 

이 원리를 활용하여 압축된 영역들도 계산해줌과 동시에 압축된 내용들의 변경 상태도 최종 반영함으로써 문제를 해결할 수가 있었습니다.

 

 

---

✏️ 코드

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

public class Main {

    private static boolean colFlip = false;
    private static boolean rowFlip = false;
    private static int turn = 0; // + 는 오른쪽으로 회전

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(st.nextToken()); // 최대 100
        int m = Integer.parseInt(st.nextToken()); // 최대 100
        int r = Integer.parseInt(st.nextToken()); // 최대 200만
        int[][] board = new int[n][m];

        for (int i = 0; i < n; ++i) {
            board[i] = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();
        }

        // r의 개수만큼 연산을 수행 (200만)
        // 1 2
        // 4 3
        // 압축 시키기
        // 내용들은 좌표에 맞춰서 압축시키기
        // 정규화 작업을 진행하기
        int[][] compositions = {{1, 2}, {4, 3}}; // 압축 배열들 (이걸 가지고 연산을 진행할 예정)
        Map<Integer, int[][]> map = new HashMap<>(); // 압축 배열들의 내용 정보 저장용
        putMapInfo(board, map, n, m); // map에 압축한 내용에 따른 배열 정보가 다 적혀있음

        st = new StringTokenizer(br.readLine()); // 명령들 입력 받기

        // 가지고 있는 압축 좌표들을 활용하여 진행하기
        while (st.hasMoreTokens()) {
            int oper = Integer.parseInt(st.nextToken());

            switch (oper) {
                case 1:
                    oper1(compositions); // 상하 반전
                    if (turn % 2 == 0) {
                        rowFlip = !rowFlip;
                    } else { // 홀수번 회전된 상태에서 반전하는 상황이라면 열을 반전시켜야 함.
                        colFlip = !colFlip;
                    }
                    break;

                case 2:
                    oper2(compositions); // 좌우 반전
                    if (turn % 2 == 0) {
                        colFlip = !colFlip;
                    } else {
                        rowFlip = !rowFlip;
                    }
                    break;

                case 3:
                    compositions = oper3(compositions); // 시계 방향으로 회전
                    ++turn;
                    turn %= 4;
                    break;

                case 4:
                    compositions = oper4(compositions); // 반시계 방향으로 회전
                    turn = --turn + 4;
                    turn %= 4;
                    break;

                case 5:
                    compositions = oper5(compositions); // 각 사분면을 시계 방향으로 회전
                    break;

                case 6:
                    compositions = oper6(compositions); // 각 사분면을 반시계 방향으로 회전
                    break;
            }
        }

        // 홀수번 회전한 경우면 n, m이 바뀌어야 함.
        if (turn % 2 != 0) {
            int temp = n;
            n = m;
            m = temp;
        }

        int[][] result = new int[n][m];
        // 압축된 내용들을 수정해주기
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                int[][] content = map.get(compositions[i][j]);

                if (rowFlip) { // 상하반전 처리해주기
                    oper1(content);
                }

                if (colFlip) {
                    oper2(content);
                }

                if (turn > 0) {
                    for (int k = 0; k < turn; ++k) {
                        content = oper3(content);
                    }
                }

                // result에 넣어주기
                if (i == 0 && j == 0) { // 1사분면 영역이라면
                    for (int a = 0; a < n / 2; ++a) {
                        for (int b = 0; b < m / 2; ++b) {
                            result[a][b] = content[a][b];
                        }
                    }
                    continue;
                }

                // 2사분면
                if (i == 0) {
                    for (int a = 0; a < n / 2; ++a) {
                        for (int b = m / 2; b < m; ++b) {
                            result[a][b] = content[a][b - (m / 2)];
                        }
                    }
                    continue;
                }

                // 3사분면
                if (j == 1) {
                    for (int a = n / 2; a < n; ++a) {
                        for (int b = m / 2; b < m; ++b) {
                            result[a][b] = content[a - (n / 2)][b - (m / 2)];
                        }
                    }
                    continue;
                }

                // 4사분면
                for (int a = n / 2; a < n; ++a) {
                    for (int b = 0; b < m / 2; ++b) {
                        result[a][b] = content[a - (n / 2)][b];
                    }
                }
            }
        }


        // 출력하기
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                sb.append(result[i][j]).append(" ");
            }
            sb.append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }

    // 상하 반전 (행 반전)
    private static void oper1(int[][] arr) {
        // compositions 처리
        // 1 2
        // 4 3
        int n = arr.length;
        int half_n = arr.length / 2;
        int m = arr[0].length;
        for (int j = 0; j < m; ++j) {
            for (int i = 0; i < half_n; ++i) {
                int temp = arr[i][j];
                arr[i][j] = arr[n - 1 - i][j];
                arr[n - 1 - i][j] = temp;
            }
        }
    }

    // 좌우 반전
    private static void oper2(int[][] arr) {
        int n = arr.length;
        int m = arr[0].length;
        int half_m = m / 2;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < half_m; ++j) {
                int temp = arr[i][j];
                arr[i][j] = arr[i][m - 1 - j];
                arr[i][m - 1 - j] = temp;
            }
        }
    }

    // 오른쪽으로 90도 회전
    private static int[][] oper3(int[][] arr) {
        int n = arr.length;
        int m = arr[0].length;
        int[][] result = new int[m][n];

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                result[i][j] = arr[n - 1 - j][i];
            }
        }
        return result;
    }

    // 왼쪽으로 90도 회전
    private static int[][] oper4(int[][] arr) {
        int n = arr.length;
        int m = arr[0].length;
        int[][] result = new int[m][n];

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                result[i][j] = arr[j][m - 1 - i];
            }
        }

        return result;
    }

    // 시계 바향으로 그룹 이동
    private static int[][] oper5(int[][] compositions) {
        int[][] result = new int[2][2];

        result[0][0] = compositions[1][0];
        result[0][1] = compositions[0][0];
        result[1][1] = compositions[0][1];
        result[1][0] = compositions[1][1];

        return result;
    }

    // 반시계 방향으로 그룹 이동
    private static int[][] oper6(int[][] compositions) {
        int[][] result = new int[2][2];

        result[0][0] = compositions[0][1];
        result[0][1] = compositions[1][1];
        result[1][1] = compositions[1][0];
        result[1][0] = compositions[0][0];

        return result;
    }

    private static void putMapInfo(int[][] board, Map<Integer, int[][]> map,
                                   int n, int m) {
        int half_n = n / 2;
        int half_m = m / 2;

        // 1사분면 내용 넣기
        int[][] one = new int[half_n][half_m];
        for (int i = 0; i < half_n; ++i) {
            for (int j = 0; j < half_m; ++j) {
                one[i][j] = board[i][j];
            }
        }
        map.put(1, one);

        // 2사분면 내용 넣기
        int[][] two = new int[half_n][half_m];
        for (int i = 0; i < half_n; ++i) {
            for (int j = half_m; j < m; ++j) {
                two[i][j - half_m] = board[i][j];
            }
        }
        map.put(2, two);

        // 3사분면 내용 넣기
        int[][] three = new int[half_n][half_m];
        for (int i = half_n; i < n; ++i) {
            for (int j = half_m; j < m; ++j) {
                three[i - half_n][j - half_m] = board[i][j];
            }
        }
        map.put(3, three);

        // 4사분면 내용 넣기
        int[][] four = new int[half_n][half_m];
        for (int i = half_n; i < n; ++i) {
            for (int j = 0; j < half_m; ++j) {
                four[i - half_n][j] = board[i][j];
            }
        }
        map.put(4, four);
    }
}