[JAVA] 17406 - 배열 돌리기 4 💛4 : 복잡한 2차원 배열 문제는 복잡도를 줄이기 위해 1차원으로 뽑자!

들어가며

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

(r, c, s) 식으로 연산이 주어지는데, (r-s, c-s)와 (r+s, c+s)로 정사각형을 잡고 해당 부분을 한줄씩 시계방향으로 밀어서 행 별 최소값을 출력하면 되는 문제이다. 좀 복잡한 2차원 배열 시뮬레이션 문제이다.

본론으로

결론부터 말하자면 정말 복잡했다... 배열 회전에 관해서 이해도가 있지 않다면 제한시간 안에는 절대 못풀 거 같은 문제이다...

처음에는 문제에서 주어진 요구사항 그대로 회전하는 것을 구현했다.

public class Main {

    static int Y, X, K, ret;
    static List<Order> orders;
    static int[] visited;

    static class Order {
        Node start;
        Node end;

        Order(Node start, Node end) {
            this.start = start;
            this.end = end;
        }
    }

    static class Node {
        int y;
        int x;

        Node(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    static void go(int[][] maps, int idx) {
        if (idx == orders.size()) {
            // A값 최신화
            ret = Integer.min(ret, findA(maps));
            return;
        }

        for (int i = 0; i < orders.size(); i++) {
            if (visited[i] == 1) {
                continue;
            }
            // 회전
            visited[i] = 1;
            go(rotate(maps, orders.get(i)), idx + 1);
            visited[i] = 0; // 순열을 뽑아야 하므로 원복 필수
        }

    }

    static int[][] rotate(int[][] maps, Order order) {
        int[][] rMaps = new int[Y][X]; // 참조 끊기
        int rotateCnt = (order.end.y - order.start.y) / 2;
        for (int i = 0; i < rotateCnt; i++) {
            // 위
            for (int j = order.start.x + i; j <= order.end.x - 1 - i; j++) {
                rMaps[order.start.y + i][j + 1] = maps[order.start.y + i][j];
            }
            // 오른쪽
            for (int j = order.start.y + i; j <= order.end.y - 1 - i; j++) {
                rMaps[j + 1][order.end.x - i] = maps[j][order.end.x - i];
            }

            // 아래
            for (int j = order.end.x - i; j >= order.start.x + 1 + i; j--) {
                rMaps[order.end.y - i][j - 1] = maps[order.end.y - i][j];
            }

            // 왼쪽
            for (int j = order.end.y - i; j >= order.start.y + 1 + i; j--) {
                rMaps[j - 1][order.start.x + i] = maps[j][order.start.x + i];
            }
        }

        for (int i = 0; i < Y; i++) {
            for (int j = 0; j < X; j++) {
                if (rMaps[i][j] == 0) {
                    rMaps[i][j] = maps[i][j];
                }
            }
        }

        return rMaps;
    }

    static int findA(int[][] maps) {
        int cnt = Integer.MAX_VALUE;

        for (int i = 0; i < Y; i++) {
            int sum = 0;
            for (int j = 0; j < X; j++) {
                sum += maps[i][j];
            }
            cnt = Integer.min(cnt, sum);
        }
        return cnt;
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Y = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        int[][] maps = new int[Y][X];

        for (int i = 0; i < Y; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < X; j++) {
                maps[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        orders = new ArrayList<>();

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());

            orders.add(new Order(new Node(r - s - 1, c - s - 1), new Node(r + s - 1, c + s - 1)));
        }

        ret = Integer.MAX_VALUE;
        visited = new int[K];
        go(maps, 0);

        System.out.println(ret);
    }
}

이 문제의 핵심은 연산으로 주어지는 (r,c,s)가 정사각형을 만든다는 것이다. 그래서 (order.end.y - order.start.y) / 2로 rotateCnt를 구한 것을 볼 수 있다. 하지만 이 풀이는 솔직히 너무 실수하기 쉽다. rotate() 메서드만 봐도 집중해서 하지 않으면 무조건 실수한다. 지금 다시봐도 너무 더럽다.

 

다른 분들도 나처럼 풀었나... 해서 봤는데, 전혀 아니었다.

회전할 값들을 뽑은다음에 하나씩 밀어주자!

인덱스로 밀어주는 것은 너무 헷갈리기에 회전할 값들을 뽑아서 하나씩 밀어주는 것이다!! 처음 봤을때 엄청 혁신적이었다.

즉, 아래와 같은 그림이다.

// 그전에 너무 복잡했던 방법
1 2 3    8 1 2
8 9 4 -> 7 9 3 
7 6 5    6 5 4

// 아래처럼 하나씩 밀 것들을 뽑은 다음, 밀고 나서 그 위치에 배치하자.
1, 2, 3, 4, 5, 6, 7, 8 -> 8, 1, 2, 3, 4, 5, 6, 7

그렇다면, 로직이 아래와 같이 변신한다!!

public class Main {

    static int N, M, K;
    static int ret = Integer.MAX_VALUE;
    static int[][] origin;
    static Rotation[] ops;
    static Rotation[] selected;
    static boolean[] visited;

    static class Rotation {
        int r, c, s;

        Rotation(int r, int c, int s) {
            this.r = r;
            this.c = c;
            this.s = s;
        }
    }

    static class Point {
        int y, x;

        Point(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    static void perm(int idx) {
        if (idx == K) {
            int[][] copy = copyMap(origin);

            for (int i = 0; i < K; i++) {
                rotate(copy, selected[i]);
            }

            ret = Math.min(ret, getMin(copy));

            return;
        }

        for (int i = 0; i < K; i++) {
            if (visited[i]) {
                continue;
            }
            visited[i] = true;
            selected[idx] = ops[i];
            perm(idx + 1);
            visited[i] = false;
        }
    }

    static void rotate(int[][] map, Rotation op) {
        int r = op.r;
        int c = op.c;
        int s = op.s;

        for (int layer = 1; layer <= s; layer++) {
            int top = r - layer;
            int left = c - layer;
            int bottom = r + layer;
            int right = c + layer;

            List<Point> positions = new ArrayList<>();
            List<Integer> values = new ArrayList<>();

            // 위쪽: 좌 -> 우
            for (int i = left; i < right; i++) {
                positions.add(new Point(top, i));
            }
            // 오른쪽 : 상 -> 하
            for (int i = top; i < bottom; i++) {
                positions.add(new Point(i, right));
            }
            // 아래 : 우 -> 좌
            for (int i = right; i > left; i--) {
                positions.add(new Point(bottom, i));
            }
            // 왼쪽 : 하 -> 상
            for (int i = bottom; i > top; i--) {
                positions.add(new Point(i, left));
            }

            for (Point p : positions) {
                values.add(map[p.y][p.x]);
            }

            int last = values.get(values.size() - 1);
            for (int i = values.size() - 1; i > 0; i--) {
                values.set(i, values.get(i - 1));
            }
            values.set(0, last);

            for (int i = 0; i < positions.size(); i++) {
                Point p = positions.get(i);
                map[p.y][p.x] = values.get(i);
            }
        }
    }

    static int getMin(int[][] map) {
        int min = Integer.MAX_VALUE;

        for (int i = 0; i < N; i++) {
            int sum = 0;
            for (int j = 0; j < M; j++) {
                sum += map[i][j];
            }
            min = Math.min(min, sum);
        }

        return min;
    }

    static int[][] copyMap(int[][] map) {
        int[][] copy = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                copy[i][j] = map[i][j];
            }
        }
        return copy;
    }

    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());
        K = Integer.parseInt(st.nextToken());

        origin = new int[N][M];

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

        ops = new Rotation[K];
        selected = new Rotation[K];
        visited = new boolean[K];

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken()) - 1;
            int s = Integer.parseInt(st.nextToken());

            ops[i] = new Rotation(r, c, s);
        }

        perm(0);
        System.out.println(ret);
    }
}

새로운 자료구조를 회전때마다 생성하므로 시간자체는 3배나 느려지지만, 인덱스로 하면 너무나도 실수하기 쉽기에 이 풀이가 훨씬 더 좋은 것 같다. 

마무리하며

이렇게 2차원 배열의 원소들을 인덱스 기반으로 스위칭하는 것이 아니라, 변경할 것들을 미리 뽑고 변경을 한다음 뽑았던 자리에 배치한다는 생각!!!! 너무 혁신적이다. 실수를 확 줄일 수 있을 것 같다!!

배열에 관해서 이해도가 한단계 올라가게 해준 고마운 문제였다 🙇‍♂️