[BaekJoon] 16954 움직이는 미로 탈출 (Java)

1.  문제 링크

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

2.  문제

요약

• 욱제는 8 x 8 크기의 체스판에서 탈출하는 게임을 만들었는데, 체스판의 모든 칸은 빈 칸 또는 벽 중 하나입니다.
• 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 합니다.
• 이 게임은 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라집니다.
• 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있습니다. 이동할 때는 빈 칸으로만 이동할 수 있습니다.
• 1초 동안 욱제의 캐릭터가 먼저 이동하고, 그 다음 벽이 이동합니다.
• 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없습니다.
• 욱제의 캐릭터가 가장 오른쪽 윗 칸으로 이동할 수 있는지 없는지 구하는 문제입니다.
• 입력: 8개의 줄에 걸쳐 체스판의 상태가 주어집니다. '.'은 빈 칸, '#'은 벽입니다. 가장 왼쪽 아랫칸은 항상 벽이 아닙니다.
• 출력: 첫 번째 줄에 욱제의 캐릭터가 가장 오른쪽 윗 칸에 도착할 수 있으면 1을, 없으면 0을 출력합니다.

3.  소스코드

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

public class Main {
    static final int SIZE = 8;
    static int[] dx = {0, -1, -1, 0, 1, 1, 1, 0, -1}, dy = {0, 0, 1, 1, 1, 0, -1, -1, -1};
    static char[][] map;
    static Queue<CharacterLoc> locs;

    static void input() {
        Reader scanner = new Reader();
        map = new char[8][8];
        locs = new LinkedList<>();

        for(int row = 0; row < SIZE; row++) {
            String info = scanner.nextLine();
            for(int col = 0; col < SIZE; col++)
                map[row][col] = info.charAt(col);
        }
    }

    static void solution() {
        locs.offer(new CharacterLoc(SIZE - 1, 0));
        System.out.println(bfs() ? 1 : 0);
    }

    static boolean bfs() {
        while(!locs.isEmpty()) {
            int size = locs.size();

            for(int count = 0; count < size; count++) {
                CharacterLoc cur = locs.poll();

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

                for(int dir = 0; dir < 9; dir++) {
                    int cx = cur.x + dx[dir], cy = cur.y + dy[dir];

                    if(isInMap(cx, cy)) {
                        if(cx == 0 && cy == 7) return true;
                        if(map[cx][cy] == '.')
                            locs.offer(new CharacterLoc(cx, cy));
                    }
                }
            }

            moveWalls();
        }

        return false;
    }

    static boolean isInMap(int x, int y) {
        if(x >= 0 && x < SIZE && y >= 0 && y < SIZE) return true;
        return false;
    }

    static void moveWalls() {
        for(int row = SIZE - 1; row >= 0; row--) {
            for(int col = SIZE - 1; col >= 0; col--) {
                if(row - 1 < 0) map[row][col] = '.';
                else map[row][col] = map[row - 1][col];
            }
        }
    }

    static class CharacterLoc {
        int x, y;

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

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }

            return str;
        }
    }
}

4.  접근

• 캐릭터의 위치를 나타내는 CharacterLoc 클래스를 정의합니다.
  • 캐릭터가 위치한 곳의 행의 값 x와 열의 값 y를 멤버 변수로 가집니다.
• BFS 시에 탐색을 위해 활용할 locs라는 Queue를 생성하고 처음 위치인 (7, 0)을 CharacterLoc 객체로 생성하여 Queue에 넣습니다.
• BFS를 통해 캐릭터가 오른쪽 위, 즉 (0, 7)로 이동할 수 있는지 확인합니다.
  • 현재 locs에 들어있는 원소의 개수를 size라는 변수에 저장합니다. 각 초마다 이동할 수 있는 위치를 찾고 벽을 이동시켜야 하기 때문에 이렇게 locs에 들어있는 개수만큼 진행하고 벽을 이동시키기 위해 size라는 변수를 사용할 것입니다.
  • locs에서 size번만큼 CharacterLoc 객체를 뽑아 다음 탐색에 이용할 이동할 수 있는 인접한 위치를 찾습니다.
    • 인접한 8방향을 보고 우선 체스판 내에 해당 위치가 위치하는지 확인합니다.
    • 만약 그렇다면, 그 때 해당 위치가 (0, 7)이라면 목적지에 도달할 수 있음을 나타내므로 true를 반환합니다.
    • 그렇지 않다면 해당 위치가 빈 칸인지 확인한 후에 만약 그렇다면 해당 위치를 CharacterLoc 객체로 만들어 locs에 다음 탐색을 위해 추가합니다.
  • size번만큼 돌았을 때 아직 (0, 7)까지 도달할 수 없다면 벽을 이동시킵니다.
  • locs가 비워질 때까지 true를 반환하지 못했다면, 즉 (0, 7)에 도달하지 못했다면 (0, 7)에 도달할 수 없는 것이므로 false를 반환합니다.
• BFS 결과에 따라 true라면 1을, false라면 0을 출력합니다.