[자바] 백준 22949 - 회전 미로 탐색 (java)

 문제 : boj22949

---

 

필요 알고리즘 개념

• BFS (너비 우선 탐색)
  • 탈출 까지의 최소 이동시간을 빠르게 알 수 있기 위해 BFS를 사용해야 한다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  오랜만에 재밌는 BFS 문제였다. BFS를 이해하는데 도움이 많이될 것 같은 문제로, 풀어보면 도움이 많이될 것 같다.

 

  우선 이 문제는 BFS를 상당히 잘 이해하고 있어야 풀 수 있다. 다른거 안들어간 순수 BFS 문제중에서는 거의 최상급이라 생각된다. 이 문제를 풀기위한 BFS 지식은 내가 적어놓은 BFS 글의 내용으로 충분하니, 아직 BFS를 잘 이해하지 못했다고 생각하면 한번 읽어보자. 특히 '배열에서 상하좌우로 인접한 경우에만 BFS가 가능할까?' 부분과 '방문체크에 대해 좀 더 써봄' 부분을 이해해야 한다. 그리고 선행으로 '풀어보기' 부분의 6번 '벽 부수고 이동하기'는 풀고나서 이걸 풀어야 좋을 것 같다.

 

 

2023-01-18 추가

추가로 질문이 들어와서 답변드린 내용 글에도 써놓습니다! 문제에서는 이동 후 회전하는데, 왜 'if (v[nd][nr][nc] || arr[nd][nr][nc] == '#') continue; // 방문체크는 여기서 해준다.' 부분에서 이미 회전 후 체크하는지에 대한 질문이었습니다.

1. Bfs에서 방문체크는 결국 모든 경우를 체크할 수 있어야함 (동일한 경우에 더 늦게 도착하는건 무조건 손해이므로) 2. 이 문제에서 모든경우는 해당 구역에 회전이 몇번 된 후 도착했는지임. 4번회전하면 원래대로이이 총 4가지 경우. 3. 그럼 회전하지 않고 이동하려면 방문체크에 몇번째 순서인지까지 포함되서 방문체크해야하므로 난이도 급상승! 3. 그러니 일단 다음번 이동할곳(이미 회전한곳에 이동한다고 생각)의 좌표를 확잉하고 회전한 지도 기준으로 방문체크를 해야 편합니다!

 

---

 

  우선 단순하게 이 문제를 푸는 로직을 의식의 흐름에 따라 머리로 짜보자. 대충 문제에서 제시된 것처럼 N=2인 경우의 임의의 데이터를 상상해서 진행해본다. 문제에서 제시된대로 인덱스가 1로 시작하는걸 기준으로 작성했다.

 

1. 원본 배열은 original[][]이라는 배열에 담아두고, '현재 서 있는 부분을 포함하는 구역을 제외한 나머지 구역들은 맨 처음에 주어진 방향으로 다시 돌아간다.'라는 부분을 처리하려면 원본은 유지해야 하므로, map[][]이라는 배열에 original을 모두 복사한 후, bfs를 S에서 시작한다. S는 (3,4) 였다.

 

2. 상하좌우 및 제자리로 bfs를 진행한다. 좌측은 벽이여서 제외하고, S에서 제자리(3,4), 위(2,4), 오른쪽(3,5), 아래(4,4)로 진행했다.

 

3. 큐에서 뽑혀나온 녀석은 (3,4)였고 구역은 S와 동일한 파란색 위치이다. map에서 해당 구역을 90도 회전시킨다. 그 이외의 부분은 original[][]을 기준으로 다시 초기화 해준다. -> 뭔 BFS 단 한번 진행했는데 O((4N)^2) 필요하다.

 

4. 회전시키고 보니 방문체크는 어떻게 할지 고민이다. 당연히 안해주면 시간초과가 날 수 밖에 없다. 근데 상하좌우로 항상 이동하는게 아니고 제자리에 머물수도 있는데..? 물론 4번하면 제자리긴 하지만 어떻게 체크하지? 게다가 상하좌우로 이동하면서 판까지 회전하다보니 괜히 잘못 방문체크하면 원래 갈 수 있는데, 회전때문에 못가게 될 수도 있을 것 같다.

 

5. 아무튼 좀 더 봐보자. 이번엔 큐에서 뽑힌게 (2,4)이다. (2,4) 이전 녀석은 S였고 같은 구역이므로 사실 original 기준으로 한번만 돌려야한다. 근데 이미 '3'에서 돌려버렸다! 이건 또 어떻게 체크를 해주나.. 아무튼 안돌려도 되네..

 

6. 이번엔 오른쪽(3,5)이다. 구역이 주황색으로 바껴버렸다. 주황색 부분만 90도 회전해주고 나머진 original을 복사해 맞춰준다. 또 O((4N)^2)이 들어버렸다.. 뭔가 이러면 안될 것 같다.

 

7.  이번엔 (4,4)이다. 또 구역이 파란색이 되었다. 또 파란부분 회전해주고 나머진 original 기준으로 돌려줘야 한다.

 

.....

 

---

 

  이 문제를 풀려면 중간중간 복잡한 로직들을 단순화 시키고 감싸서 간단하게 작동하도록 만들어줘야 한다. 위에서 나이브하게 생각하는 동안 문제가 됬던 부분들을 단순화 시키거나, 명확히 할 방법을 한번 찾아보자. 이하에서 나오는 'r'과 'c'는 문제에서 제시된 'y'와 'x'이다. 개인적으로 y, x 형태로는 어떻게 하든 불편해서(문제마다 x가 row를 뜻할때가 있다.) r(row), c(column)를 즐겨 사용한다. 또한 설명은 인덱스 0번부터 시작한다. (즉, n=2 라면 r은 0~7, c도 0~7 이다.)

 

 

 

A. 방문체크(방문배열)란 것은, BFS에서 '모든 경우'를 살펴보며 진행할 때, 같은 행위를 두번하면 비효율적이니 그걸 막기 위해 사용한다. 따라서 방문체크는 BFS를 진행할 때 탐색할 수 있는 '모든 경우'를 나타낼 수 있어야 한다.

  '4'에서 발생했던 문제부터 해결해보자. 이 문제에서 모든 경우를 나타내려면 3차원으로 체크해주면 된다. v[d][r][c] 형태의 방문체크 배열을 생각해보자. d는 현재 돌아간 각도를 나타낸다 (0:0도, 1:90도, 2:180도, 3:270도). r과 c는 행과 열 번호를 나타낸다. 이런식으로 둬야만 서로 충돌나는 부분 없이 모든 경우를 볼 수 있다. 또한 제자리에서 계속 돌아도 문제가 생기지 않는다.

 

  이하의 1~7의 그림은 방문체크가 채워지는 과정을 나타낸다. '1'에서 S에서 시작하면서 제자리, 오른쪽, 아래를 넣는다. 하지만 사실 그건 d=1 인 방문체크에다가 방문체크를 한거다(그게 '2' 그림이다). '2'에서도 진행 가능한곳을 진행하는데, 마찬가지로 d=2에다가 방문체크를 하는거다(그게 '3'). 이런식으로 진행 시 이제 '5'에 오게되면 'S' 위치는 더이상 갈 필요가 없게 된다. 왜냐하면 이미 '1'에서 '더 빠른 횟수로' 해당 위치에 존재했었기 때문에 다시 S부터 시작하는건 전혀 의미가 없고 그 이후로는 시간복잡도 낭비이기 때문이다. '6'과 '7'도 마찬가지로 이미 '2', '3'에 갔던 곳은 빠지면서 진행하는걸 볼 수 있다.

 

 

B. 구역번호 알기

  이 부분은 위에서 문제가 됬던건 아니지만, 헷갈릴 수 있을 것 같아 적어본다. 어쨌든 4x4 형태로 된 각 위치마다 구분만 되면 된다. 임의로 정해도 전혀 상관이 없다. 내 경우엔 아래와 같이 정의했다. 우선 범위를 벗어나면 -1을 리턴하는 부분이 있는데, 어차피 이후 bfs를 진행할 때 범위 벗어나는 부분은 체크해줘야 하는 부분이고 매번 구역도 체크해야 하므로, 범위가 벗어난건 구역이 존재하지 않는 셈이니 설계적으로도 문제 없을 것 같아 이 함수에서 역할을 담당하게 했다.

 

  구역 번호는 문제에서 제시된 방식이랑 같은데, 0부터 시작하기만 한다.

private int getDivision(int r, int c) {
    if (r<0 || c<0 || r>=4*n || c>=4*n) return -1;
    return r/4*4+c/4;
}

 

 

C. 지도를 해당 구역은 회전시키고, 나머지는 되돌리는게 너무 비효율적이에요! 

  위에서 생각해볼 때 가장 문제가 됬던 부분이다. 구현도 어렵거니와, 시간 복잡도 상에서 bfs 탐색 한 번 진행할 때 마다 O((4N)^2) 씩 필요하니 너무 비효율적이었다.

 

  이건 생각보다 간단한데, 그냥 미리 돌려두면 된다 ㅋㅋ. arr[d][r][c]를 방문체크때와 동일하게 d=0일 때 0도, d=1일 때 90도, d=2일때 180도, d=3일때 270도 돌려둔 배열이라 생각해보자. arr[0][r][c]에는 원래 입력된 데이터가 있을 것이다. 그리고 입력받으면서 미리 나머지도 다 채워놔주면 된다. 이하 코드의 주석을 참고해보자.

char[][][] arr = new char[4][n*4][n*4];
    Pos start = null;
    for (int i = 0; i < 4*n; i++) {
        String row = br.readLine();
        for (int j = 0; j < 4*n; j++) {
            char c = row.charAt(j);
            arr[0][i][j] = c;	// 원본 데이터는 arr[0][r][c]에 들어간다.
            if (c=='S') {
                start = new Pos(i, j, 0, 0);
            }
            int tmpI = i;
            int tmpJ = j;
            for (int x = 1; x <= 3; x++) {
                int[] nextPos = getRotatedPos(tmpI, tmpJ);	// 매번 90도 돌아간 좌표를 획득
                tmpI = nextPos[0];
                tmpJ = nextPos[1];
                arr[x][tmpI][tmpJ] = c;	// arr[d][r][c]에 미리 회전된 데이터를 넣어준다.
            }
        }
    }

 

  문제에서 제시된 예제 입력 3의 경우, d에 따라 미리 전처리 해서 돌려둔 배열의 모습은 다음과 같다.

0
#S#.#.##
#...E#.#
#.##.##.
#....###
#.#..##.
#......#
#..##..#
########
-----------------------
1
####..E#
...S###.
.#.###.#
.#..#.##
######..
#...#..#
#..##..#
##..###.
-----------------------
2
...####.
##.#.##.
...##.#E
.#S###.#
########
#..##..#
...##...
.#.#.##.
-----------------------
3
..#.##.#
#.#.#.##
S....###
#####E..
..##.###
#..##..#
...##..#
####..##

즉, 도형들이 4x4 안의 데이터라고 봤을 때, 이렇게 돌아간다.

 

 

D. 근데 90도 돌아간 좌표 위치를 어떻게 알아요?

  4x4로 나눠진 구역에 대해서만 돌아가야 하므로 상당히 헷갈릴 수 있는데, 좀 단순화해서 그냥 4x4 배열을 회전시킨다고 생각해보자. 그건 간단하게 가능할꺼다. 수식으로 작성해봐도 (r, c) -> (c, 4-1-r) 을 해주면 되고, 수식을 못세우겠다면 그냥 미리 정한 규칙대로 매핑시켜도 된다. 예를들어 (0,0) -> (0,3), (0,1) -> (1,3)... 이런식으로 16개만 미리 정해두면 된다.

 

  근데 실제론 4x4로 나눠진 구역에 대해 진행해야하는데 4x4 배열로만 생각하면 어떻게 하냐면, 만약 (5,13) 이라고 해보자. 거기서 r=4, c=12 만큼은 사실 확정된 다른 구역이다. 어차피 해당 r,c가 포함된 구역은 저 확정된 부분을 빼고 생각해도 된다. 즉, 4랑 12는 따로 저장해두고(코드의 baseR, baseC. 4로 나눠서 내림처리를 해주고 다시 4를 곱해주면 된다.), 남은 (1, 1)만 가지고 4x4 배열로 생각해서 돌려주면 된다.

private int[] getRotatedPos(int r, int c) {
    int baseR = r/4*4;
    int baseC = c/4*4;
    r %= 4;
    c %= 4;
    return new int[]{baseR+c, baseC+3-r};
}

 

 

E. 이제 어느정도 해결된 것 같은데, 그럼 이제 탐색을 해보자.

  난 설명을 쓰면 항상 쓸데없이 길어지는 편이라 코드에 주석을 쓴걸 보는게 더 빠를 것 같다. 위에서 명확히 하거나, 로직을 간소화 시킨걸 모두 포함해서 일반적인 bfs를 진행해주면 된다. 물론 bfs를 이해하고 있지 않다면 짜는게 쉽진 않을거다.

boolean[][][] v = new boolean[4][n*4][n*4];	// 설명했던 방문체크 배열임
Queue<Pos> q = new ArrayDeque<>();
q.add(start);
v[0][start.r][start.c] = true;

while (!q.isEmpty()) {
    Pos cur = q.poll();
    int r = cur.r;
    int c = cur.c;
    int d = cur.d;	// d는 현재 봐야할 각도이다. 미리 배열로 만들어뒀으니 arr[d][r][c]에서 d에 해당한다.
    if (arr[d][r][c] == 'E') {	// 현재 위치가 'E'라면 종료. 물론 아래서 다음 위치 정할 때 바로 체크해도 되지만 난 이 방식을 더 선호한다.
        System.out.println(cur.dist);
        return;
    }
    int cDiv = getDivision(r, c);	// 현재 위치의 구역번호 획득(다음 진행할곳과 비교를 위해)
    for (int dir = 0; dir < 5; dir++) {	// dir은 제자리, 상하좌우를 나타낸다.
        int nr = r+DR[dir];	// dir에 따른 다음 r
        int nc = c+DC[dir];	// dir에 따른 다음 c
        int nDiv = getDivision(nr, nc);	// 다음 r,c의 구역번호
        if (nDiv == -1) continue;	// 범위 넘어간거면 패스
        int nd = cDiv == nDiv ? (d+1)%4 : 1;	// 다음 갈 구역이 현재 구역번호와 다르다면 1로 가면 된다. 같다면 d+1로 가야한다. d+1이 4이라면 0으로 가야한다.
        
        int[] nrc = getRotatedPos(nr, nc);	// 다음 진행할 곳은 회전되어야 하므로, 다음 r,c의 회전된 r,c를 구해서 큐에 넣어주려 한다.
        nr = nrc[0];	// 다음 진행할 곳의 회전된 r
        nc = nrc[1];	// 다음 진행할 곳의 회전된 c

        if (v[nd][nr][nc] || arr[nd][nr][nc] == '#') continue;	// 방문체크는 여기서 해준다.
        v[nd][nr][nc] = true;
        q.add(new Pos(nr, nc, nd, cur.dist+1));
    }
}
System.out.println(-1);

 

 

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
    class Pos{
        int r, c, d, dist;
        public Pos(int r, int c, int d, int dist) {
            this.r = r;
            this.c = c;
            this.d = d;
            this.dist = dist;
        }
    }

    private static final int[] DR = {0, 1, -1, 0, 0};
    private static final int[] DC = {0, 0, 0, 1, -1};
    int n;

    private int getDivision(int r, int c) {
        if (r<0 || c<0 || r>=4*n || c>=4*n) return -1;
        return r/4*4+c/4;
    }

    private int[] getRotatedPos(int r, int c) {
        int baseR = r/4*4;
        int baseC = c/4*4;
        r %= 4;
        c %= 4;
        return new int[]{baseR+c, baseC+3-r};
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

        n = Integer.parseInt(br.readLine());
        char[][][] arr = new char[4][n*4][n*4];
        Pos start = null;
        for (int i = 0; i < 4*n; i++) {
            String row = br.readLine();
            for (int j = 0; j < 4*n; j++) {
                char c = row.charAt(j);
                arr[0][i][j] = c;
                if (c=='S') {
                    start = new Pos(i, j, 0, 0);
                }
                int tmpI = i;
                int tmpJ = j;
                for (int x = 1; x <= 3; x++) {
                    int[] nextPos = getRotatedPos(tmpI, tmpJ);
                    tmpI = nextPos[0];
                    tmpJ = nextPos[1];
                    arr[x][tmpI][tmpJ] = c;
                }
            }
        }

        boolean[][][] v = new boolean[4][n*4][n*4];
        Queue<Pos> q = new ArrayDeque<>();
        q.add(start);
        v[0][start.r][start.c] = true;
        while (!q.isEmpty()) {
            Pos cur = q.poll();
            int r = cur.r;
            int c = cur.c;
            int d = cur.d;
            if (arr[d][r][c] == 'E') {
                System.out.println(cur.dist);
                return;
            }
            int cDiv = getDivision(r, c);
            for (int dir = 0; dir < 5; dir++) {
                int nr = r+DR[dir];
                int nc = c+DC[dir];
                int nDiv = getDivision(nr, nc);
                if (nDiv == -1) continue;
                int nd = cDiv == nDiv ? (d+1)%4 : 1;
                int[] nrc = getRotatedPos(nr, nc);
                nr = nrc[0];
                nc = nrc[1];

                if (v[nd][nr][nc] || arr[nd][nr][nc] == '#') continue;
                v[nd][nr][nc] = true;
                q.add(new Pos(nr, nc, nd, cur.dist+1));
            }
        }
        System.out.println(-1);
    }

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