[코드트리] 메이즈 러너 - java

문제

https://www.codetree.ai/problems/maze-runner?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

접근법

크게 동작하는 것을 나누면 2가지로 나눌 수 있다.

1. 참가자들 전부 이동

2. 정사각형 찾아서 90도 시계방향으로 회전

 

매 초마다 참가자들을 이동하기 위해 참가자들의 좌표 정보를 저장하고 있어야 한다. 한 칸에 여러 참가자가 존재할 수 있으므로 2차원 배열에 참가자들의 위치를 표시하지 않고 ArrayList를 사용해 저장했다. 

 

참가자들 이동

좌표 구하기

각 참가자의 입장에서 상하좌우 중 지금보다 출구에 더 가까운 좌표로 이동하면 된다. 

X가 참가자의 위치라고 할 때, 참가자는 위로 가는 것와 왼쪽으로 가는 것 둘 다 출구에 더 가까워지면서 벽이 없기 때문에 가능하다. 이 경우 문제에서 상하를 우선시 하라고 했으므로 위로 가면 된다.

 

int[] dirR = {-1, 1, 0, 0};
int[] dirC = {0, 0, -1, 1};

이렇게 0상 1하 2좌 3우로 정의했을 때, ① 범위를 벗어나지 않고 ② 벽이 존재하지 않으며 ③ 현재 위치보다 출구가 더 가까워진 경우에만 우선 순위 큐에 넣어줬다. 

우선 순위 큐에서는 거리가 짧은 좌표에 우선 순위를 높게 주도록 설정하였고, 거리가 같은 경우 방향이 상 또는 하 (0 또는 1)인 경우가 우선시 되도록 설정해주었다. 어느 경우에서든 우선 순위 큐에 상, 하 좌표가 동시에 가장 거리가 짧은 경우는 존재하지 않으므로 고려하지 않아도 된다.

 

이동하기

우선 순위 큐에서 하나만 poll()해서 이동한다. 이때 이동해서 도착한 칸이 출구인 경우 참가자 ArrayList에서 제거해주어야 한다. 바로 제거하면 for문을 도는 동안 ArrayList의 크기가 바뀌므로 다른 ArrayList에 인덱스만 저장해 준 뒤 모든 참가자가 다 이동한 후에 제거해준다. 또한, 이동한 거리도 증가시켜준다.

private static void moveUsers() {
        Deque<Integer> success = new ArrayDeque<>();

        for (int i = 0; i < users.size(); i++) {
            PriorityQueue<Point> pq = new PriorityQueue<>(new Comparator<Point>() {
                @Override
                public int compare(Point o1, Point o2) {
                    int d1 = Math.abs(o1.r - exit.r) + Math.abs(o1.c - exit.c);
                    int d2 = Math.abs(o2.r - exit.r) + Math.abs(o2.c - exit.c);

                    if (d1 != d2) {
                        return d1 - d2;
                    }

                    // 거리가 같다면 d 값이 0이거나 1인 경우 우선순위를 높게 부여
                    if (o1.d == 0 || o1.d == 1) {
                        return -1;
                    } else if (o2.d == 0 || o2.d == 1) {
                        return 1;
                    }

                    return 0;
                }
            });

            Point user = users.get(i);
            int nowD = Math.abs(user.r - exit.r) + Math.abs(user.c - exit.c);

            // 상하좌우 중 갈 수 있는 좌표를 모두 큐에 넣는다.
            for (int j = 0; j < 4; j++) {
                int nextR = user.r + dirR[j];
                int nextC = user.c + dirC[j];
                int nextD = Math.abs(nextR - exit.r) + Math.abs(nextC - exit.c);

                if (rangeIn(nextR, nextC) && (nextD < nowD) && (map[nextR][nextC] == 0 || map[nextR][nextC] == EXIT)) {
                    pq.offer(new Point(nextR, nextC, j));
                }
            }

            if (pq.isEmpty()) {
                continue;
            }

            Point next = pq.poll();
            user.r = next.r;
            user.c = next.c;
            sum++;

            // 미로를 탈출한 경우
            if (map[user.r][user.c] == EXIT) {
                success.offer(i);
            }
        }

        // 탈출한 사람들 리스트에서 제거
        while (!success.isEmpty()) {
            users.remove(success.pollLast().intValue());
        }
    }

여기서 탈출한 사람들을 제거할 때 주의할 점은 리스트로 저장했든 큐로 저장했든 간에 뒤 부터 제거해주어야 한다는 점이다. 탈출한 사람을 저장하는 큐에는 인덱스가 순서대로 들어있을 것이고, 그 순서대로 원래 참가자 리스트에서 remove를 해준다면 인덱스가 꼬이기 때문이다.

 

정사각형 찾기

원래 출구와 가장 가까운 참가자를 찾고, 정사각형의 길이를 구한 다음 (1, 1)에서 해당 길이만큼의 정사각형을 반복해서 돌리며 출구와 가까운 참가자가 둘다 포함되는 것이 아닐까? 했는데 아니였다. '가장 가까운 참가자'라는 정의가 문제에서 정확히 주어지지 않았으므로 애초에 생각하지 말았어야 한다...

 

정사각형을 찾기 위해서는 정사각형 한 변의 길이 2~N을 전부 완전탐색해서 찾아야 한다. 매번 참가자 중 한명이라도 포함되는지 검사하면 된다. 출구는 무조건 포함되어야 하므로 출구가 포함되지 않는 경우는 스킵해서 참가자가 포함됐는지 검사하는 연산을 안 하도록 주의 해야한다.

// 정사각형 구하기
for (int length = 2; length <= N; length++) {
    for (int r = 1; r <= (N - length + 1); r++) {
        for (int c = 1; c <= (N - length + 1); c++) {
            // 출구가 정사각형에 포함되지 않는 경우
            if (!(exit.r >= r && exit.r < r + length) || !(exit.c >= c && exit.c < c + length)) {
                continue;
            }

            for (Point user: users) {
                if ((user.r >= r && user.r < r + length) && (user.c >= c && user.c < c + length)) {
                    rotate(new Point(r, c), length);
                    return;
                }
            }
        }
    }
}

 

정사각형 회전

(1, 1)에서 길이가 4인 정사각형을 시계 방향으로 90도 회전하게 되면 1행 -> N열, 2행 -> N - 1열..이 되고 1열 -> 1행, 2열 -> 2행이 된다. 여기서 규칙을 찾을 수 있다. 구하는 과정이 있긴 한데 이런 식으로 구하는게 맞는건진.. 모르겠지만 접은 글로 첨부해보겠당

1행 -> N열

2행 -> N - 1열

3행 -> N - 2열

...

 

여기서 행 번호와 열 번호를 더했을 때 항상 N + 1이 나온다는 것을 활용해 열 번호를 구하는 수식을 구했다.

 

R행 -> N + x열 이라고 가정하면 R + x = 1이어야 한다.

여기서 식을 정리해주면 x = 1 - R 이 된다. 따라서

 

R행 -> N + 1 - R열

을 구할 수 있다!

int newR = c;
int newC = N + 1 - r;

이 수식을 사용해 정사각형을 회전시켜도 되지만 좀 복잡해서 이 수식은 참가자들을 회전시킬 때 사용했다..

 

(1, 2)에서 길이가 3인 정사각형을 회전하는 경우를 생각해보자. 

 

rotatedArr[1][2] = arr[3][2]

rotatedArr[1][3] = arr[2][2]

rotatedArr[1][4] = arr[1][2]

 

rotatedArr[2][2] = arr[3][3]

rotatedArr[2][3] = arr[2][3]

rotatedArr[2][4] = arr[1][3]

 

rotatedArr[3][2] = arr[3][4]

rotatedArr[3][3] = arr[2][4]

rotatedArr[3][4] = arr[1][4]

 

(1, 2)를 start.r와 start.c로 나타내고 길이가 3이라는 것을 length라고 했을 때, rotatedArr의 각 행마다 열은 (start.r + length - 1)에서 하나씩 줄어드는 것을 확인할 수 있다. rotatedArr에서 각 행은 start.c이 증가하는 것도 확인할 수 있다. 이를 바탕으로 반복문을 작성하면 아래와 같다.

int c = start.c;
for (int i = start.r; i < (start.r + n); i++) {
    int r = start.r + n - 1;
    for (int j = start.c; j < (start.c + n); j++) {
        tmp[i][j] = map[r][c];
        r--;
    }
    c++;
}

 

정사각형이 회전할 때 정사각형 안에 있는 참가자들도 회전해줘야 한다.

// 미로에 포함되어 있는 유저 위치 회전
for (Point user: users) {
    if (user.r >= start.r && user.r < (start.r + n) && user.c >= start.c && user.c < (start.c + n)) {
        // 정사각형의 상대적인 위치
        int tmpR = user.r - start.r;
        int tmpC = user.c - start.c;

        user.r = start.r + tmpC;
        user.c = start.c + n - 1 - tmpR;
    }
}

 

코드

앞에서 설명한 것을 토대로 코드를 작성하면 아래와 같다. 코드트리에 해설이 있긴 한데 변수명이 헷갈려서 그냥 내가 다시 다 작성했다.. 그래서 알고리즘이 좀 다를수도 있다.

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.List;

public class Main {

    static final int EXIT = -1;

    static int N, M, K;
    static int[][] map;
    static List<Point> users = new ArrayList<>();
    static Point exit;
    static int sum = 0;

    static int[] dirR = {-1, 1, 0, 0};
    static int[] dirC = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        map = new int[N + 1][N + 1];
        for (int r = 1; r <= N; r++) {
            st = new StringTokenizer(br.readLine());
            for (int c = 1; c <= N; c++) {
                map[r][c] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            users.add(new Point(r, c));
        }

        st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        exit = new Point(r, c);
        map[exit.r][exit.c] = EXIT;

        for (int i = 1; i <= K; i++) {
            // K초 전에 모든 참가자가 탈출한 경우
            if (users.size() == 0) {
                break;
            }
            start();
        }

        sb.append(sum).append('\n');
        sb.append(exit.r).append(' ').append(exit.c);
        System.out.println(sb);
    }

    private static void start() {
        // 1. 각 참가자마다 이동한다.
        moveUsers();

        if (users.size() == 0) {
            return;
        }

        // 2. 정사각형을 찾아서 회전한다.
        mazeRotate();
    }

    private static void moveUsers() {
        Deque<Integer> success = new ArrayDeque<>();

        for (int i = 0; i < users.size(); i++) {
            PriorityQueue<Point> pq = new PriorityQueue<>(new Comparator<Point>() {
                @Override
                public int compare(Point o1, Point o2) {
                    int d1 = Math.abs(o1.r - exit.r) + Math.abs(o1.c - exit.c);
                    int d2 = Math.abs(o2.r - exit.r) + Math.abs(o2.c - exit.c);

                    if (d1 != d2) {
                        return d1 - d2;
                    }

                    // 거리가 같다면 d 값이 0이거나 1인 경우 우선순위를 높게 부여
                    if (o1.d == 0 || o1.d == 1) {
                        return -1;
                    } else if (o2.d == 0 || o2.d == 1) {
                        return 1;
                    }

                    return 0;
                }
            });

            Point user = users.get(i);
            int nowD = Math.abs(user.r - exit.r) + Math.abs(user.c - exit.c);

            // 상하좌우 중 갈 수 있는 좌표를 모두 큐에 넣는다.
            for (int j = 0; j < 4; j++) {
                int nextR = user.r + dirR[j];
                int nextC = user.c + dirC[j];
                int nextD = Math.abs(nextR - exit.r) + Math.abs(nextC - exit.c);

                if (rangeIn(nextR, nextC) && (nextD < nowD) && (map[nextR][nextC] == 0 || map[nextR][nextC] == EXIT)) {
                    pq.offer(new Point(nextR, nextC, j));
                }
            }

            if (pq.isEmpty()) {
                continue;
            }

            Point next = pq.poll();
            user.r = next.r;
            user.c = next.c;
            sum++;

            // 미로를 탈출한 경우
            if (map[user.r][user.c] == EXIT) {
                success.offer(i);
            }
        }

        // 탈출한 사람들 리스트에서 제거
        while (!success.isEmpty()) {
            users.remove(success.pollLast().intValue());
        }
    }

    // 정사각형을 찾아서 회전
    private static void mazeRotate() {

        // 정사각형 구하기
        for (int length = 2; length <= N; length++) {
            for (int r = 1; r <= (N - length + 1); r++) {
                for (int c = 1; c <= (N - length + 1); c++) {
                    // 출구가 정사각형에 포함되지 않는 경우
                    if (!(exit.r >= r && exit.r < r + length) || !(exit.c >= c && exit.c < c + length)) {
                        continue;
                    }

                    for (Point user: users) {
                        if ((user.r >= r && user.r < r + length) && (user.c >= c && user.c < c + length)) {
                            rotate(new Point(r, c), length);
                            return;
                        }
                    }
                }
            }
        }
    }

    // (start.r, start.c) ~ (start.r + n, start.c + n) 구역을 시계 방향으로 회전
    private static void rotate(Point start, int n) {
        int[][] tmp = new int[N + 1][N + 1];

        int c = start.c;
        for (int i = start.r; i < (start.r + n); i++) {
            int r = start.r + n - 1;
            for (int j = start.c; j < (start.c + n); j++) {
                tmp[i][j] = map[r][c];
                r--;
            }
            c++;
        }

        // 미로에 포함되어 있는 유저 위치 회전
        for (Point user: users) {
            if (user.r >= start.r && user.r < (start.r + n) && user.c >= start.c && user.c < (start.c + n)) {
                // 정사각형의 상대적인 위치
                int tmpR = user.r - start.r;
                int tmpC = user.c - start.c;

                user.r = start.r + tmpC;
                user.c = start.c + n - 1 - tmpR;
            }
        }

        // 원본 배열에 복사
        for (int i = start.r; i < (start.r + n); i++) {
            for (int j = start.c; j < (start.c + n); j++) {
                map[i][j] = tmp[i][j];

                // 출구 위치 변경
                if (map[i][j] == EXIT) {
                    exit.r = i;
                    exit.c = j;
                }

                // 내구도 감소
                if (map[i][j] > 0) {
                    map[i][j]--;
                }
            }
        }
    }

    private static boolean rangeIn(int r, int c) {
        return (r > 0) && (c > 0) && (r <= N) && (c <= N);
    }

    static class Point {
        int r, c, d;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }

        public Point(int r, int c, int d) {
            this.r = r;
            this.c = c;
            this.d = d;
        }
    }
}