BOJ G3 16954 움직이는 미로 탈출 JAVA

16954번: 움직이는 미로 탈출

---

문제 읽기

처음에 딱 읽었을 때는 DFS가 생각났다. 그래서 dfs로 짜다가.. 생각해보니 벽을 피해서 움직여야 하고, 8방으로 움직여야 한다. 맵의 크기가 매우 작긴 하지만, 벽을 피해서 이동하는게 최우선이기 때문에 중복 방문도 가능하다 생각했고, 경우의 수가 너무 많이 나올 것 같았다. 맵의 벽도 계속 이동 시켜서 넘겨줘야 하는데 너무 비효율적이라는 생각이 들었다. 게다가 DFS의 재귀 + 중복 방문 허용이 합쳐지면 처리를 해주지 않는 이상 무한 루프에 빠질 가능성이 높지 않을까 하는 생각이 들었다.

 

그래서 BFS로 바꾸었다. BFS는 위의 문제를 해결해 주는 방법이다! BFS로 갈 수 있는 방향의 모든 좌표를 큐에 넣고, 한 단계씩 맵을 업데이트 해주면 되기 때문에 DFS보다 훨씬 오버헤드가 적다. 또한 중복 방문을 허용하기 때문에 다소 검사해야 할 좌표는 많지만, 모든 좌표 중 하나라도 통과하면 로직이 끝나기 때문에 훨씬 빠르게 끝난다.

그래서 BFS로 문제를 해결했다!

---

문제 풀기

로직은 크게 어렵지 않다. 그냥 bfs를 사용하면 된다.

1. 맵을 입력 받는다
2. 시작 좌표 (7, 0)을 큐에 넣는다
3. 큐가 비지 않을 동안 BFS를 수행한다.
   1. 이동한다. 8방 또는 그대로인 좌표를 계산한다
      1. 만약 계산한 좌표가 도착 지점이면 1을 출력하고 리턴한다.
      2. 해당 좌표에 벽이 없거나, 해당 좌표의 윗칸에 벽이 없으면 큐에 넣는다. (윗칸에 벽이 있으면 다음 시간에 움직이지 못하기 때문에 이동할 필요가 없다)
   2. 벽을 한 칸씩 내린다. 맨 위에는 .으로 채워준다.
4. 만약 큐가 비어 나오게 되면 도착하지 못하는 것이므로 0을 출력한다.

---

코드

package ps.ㄱSolving;

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

public class BOJ_G3_16954_움직이는미로탈출 {
    static class Pos{
        int r, c;
        int time;
        public Pos(int r, int c, int time){
            this.r = r;
            this.c = c;
            this.time = time;
        }
    }
    static int N = 8;
    static char[][] map;
    static int[] dr = {-1, 1, 0, 0, -1, -1, 1, 1};
    static int[] dc = {0, 0, -1, 1, -1, 1, -1, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        map = new char[N][N];
        for (int i = 0; i < N; i++){
            map[i] = in.readLine().toCharArray();
        }

        //dfs하면 끝이 안 날 거 같다.
        //bfs로 해보자! bfs로 하면 최소한 하나만 끝까지 가면 끝이니까!
        Queue<Pos> q = new ArrayDeque<>();
        q.offer(new Pos(7, 0, 0));
        int currentTime = 0;
        while(!q.isEmpty()){
            //1. 이동한다 - 8방 + 그대로
            while(!q.isEmpty() && q.peek().time == currentTime){
                Pos cur = q.poll();

                for (int di = 0; di < 8; di++){
                    int nr = cur.r + dr[di];
                    int nc = cur.c + dc[di];
                    if (nr < 0 || nr >= N || nc < 0 || nc >= N
                    || map[nr][nc] == '#' || (nr - 1 >= 0 && map[nr-1][nc] == '#')) continue;

                    if (nr == 0 && nc == 7){
                        System.out.println(1);
                        return;
                    }
                    q.offer(new Pos(nr, nc, cur.time+1));
                }
                if (cur.r - 1 >= 0 && map[cur.r-1][cur.c] == '#') continue;
                q.offer(new Pos(cur.r, cur.c, cur.time+1));
            }

            //2. 벽을 내린다.
            for (int i = N-1; i > 0; i--){
                for (int j = 0; j < N; j++){
                    map[i][j] = map[i-1][j];
                }
            }
            for (int j = 0; j < N ;j++){
                map[0][j] = '.';
            }
            currentTime++;
        }
        System.out.println(0);
    }
}