[백준 Baekjoon] 16954번 움직이는 미로 탈출 - JAVA

백준 Baekjoon 16954번 움직이는 미로 탈출 - JAVA

---

문제 풀이

BFS탐색을 사용하여 캐릭터를 이동 시킨다. 최초에는 처음 시작위치인 7,0을 넣고 시뮬레이션을 시작한다.


큐에서 캐릭터를 현재 케릭터들의 위치들을 꺼내와 9방향으로 이동할 수 있는지 검사하고 새로운 위치를 큐에 추가한다. 큐의 사이즈만큼만 반복하여 큐에서 캐릭터를 꺼내면 새로 추가되는 위치는 탐색하지 않게 된다.


동일한 위치에 여러 캐릭터가 이동하는 것을 방지하기 위해 visit배열을 둔다. visit배열은 매 턴이 끝날때 마다 새로 생성되어야 한다. 이전에 있었던 위치로 돌아가야 하는 상황도 존재한다.


새로운 위치로 이동시켜 큐에 추가한 위치가 벽이 이동하면서 벽과 겹쳐질 수 있어 큐에서 꺼냈을 때 검사해야 한다.


케릭터 이동이 완료되면 벽을 움직인다.


목표지점인 0,7에 도착하면 종료되며, 큐에 값이 없어 반복문이 종료되는 경우는 케릭터가 이동할 수 없는 경우이다.

소스 코드

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

public class Main {
    public static char[][] map = new char[8][8];

    public static int[] dy = {-1, 0, 1, 0, 0, -1, 1, -1, 1};
    public static int[] dx = {0, -1, 0, 1, 0, 1, -1, -1, 1};

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

        for (int i = 0; i < 8; i++) {
            map[i] = br.readLine().toCharArray();
        }

        System.out.println(bfs() ? 1 : 0);
    }

    public static boolean bfs() {
        Queue<Node> queue = new LinkedList<>();
        boolean[][] visit;

        queue.add(new Node(7, 0));

        while (!queue.isEmpty()) {
            int size = queue.size();

            visit = new boolean[8][8];

            for (int i = 0; i < size; i++) {
                Node cur = queue.poll();

                if (map[cur.x][cur.y] == '#') continue;

                if (cur.x == 0 && cur.y == 7) {
                    return true;
                }

                for (int k = 0; k < 9; k++) {
                    int nx = cur.x + dx[k];
                    int ny = cur.y + dy[k];

                    if (nx < 0 || ny < 0 || nx >= 8 || ny >= 8) continue;
                    if (visit[nx][ny] || map[nx][ny] == '#') continue;

                    queue.add(new Node(nx, ny));
                    visit[nx][ny] = true;
                }
            }

            wall_move();
        }

        return false;
    }

    public static void wall_move() {
        for (int i = 7; i >= 0; i--) {
            for (int j = 0; j < 8; j++) {
                if (map[i][j] == '#') {
                    map[i][j] = '.';

                    if (i != 7) {
                        map[i + 1][j] = '#';
                    }
                }
            }
        }
    }

    public static class Node {
        int x;
        int y;

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