알고리즘 풀이 - 백준 16954(움직이는 미로 탈출, 그래프(BFS))

 

관련글

 

그래프 관련 포스팅은 여기를 참조
DFS 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

8x8 크기의 체스판에서 가장 좌측 아래에 위치 시에 벽이 점점 내려오는 경우 상하좌우, 대각, 제자리의 9위치로 이동 가능 시 우측 최 상단으로 이동 가능한지 여부를 판별하는 문제

 

 

2. 풀이

 

이 문제는 최단 시간에 도달하는 경우를 푸는 문제는 아니지만 BFS+시뮬레이션으로 풀어야 한다.

왜냐하면, 벽이 내려올 때마다 주변의 가능한 모든 이동 가능 위치를 체크해야 하며 실제로 벽의 위치를 조정하며 문제를 해결해야 하기 때문이다.

 

현재 위치에서 모든 방향으로 이동 가능한 경우를 체크한 뒤, 벽이 0개 이상일 때, 벽을 1칸씩 아래로 재배치 후, 현재 위치가 벽이 아닌 경우에만 추가 탐색이 가능하도록 한다.

 

이 문제는 전형적인 BFS 문제로 벽을 한 칸씩 이동시키는 시뮬레이션 코드만 잘 작성하면 해결할 수 있는 문제이다.
다만, 시간 복잡도를 더 줄일 수 있는 방법이 있다.

 

① (Y, X)를 각 위치라고 할 때, Y가 0이라면 무조건 가능하다고 볼 수 있다.
  → 제일 위의 위치에 이미 도달했다면 벽을 마주칠 일이 없기 때문이다.
② 벽이 모두 내려와서 증발했다면 무조건 가능하다.

 

위 2가지의 케이스를 고려하는 코드를 추가하면 훨씬 빠른 속도로 문제를 해결할 수 있게 된다!

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

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

public class Main{
    static int n = 8;
    static int m = 8;
    static int[] dy = {-1, 0, 1, 0, 0, -1, 1, -1, 1};
    static int[] dx = {0, -1, 0, 1, 0, 1, -1, -1, 1};
    static boolean[][] map;
    static Queue<Integer> wall = new LinkedList<>();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        map = new boolean[8][8];

        for(int i=0; i < 8; i++){
            String s = br.readLine();
            for(int j=0; j < 8; j++){
                char c = s.charAt(j);

                // 벽이라면 해당 위치 저장하고 true 로 지정
                if(c == '#') {
                    wall.offer(i * 8 + j);
                    map[i][j] = true;
                }
            }
        }

        // BFS를 수행하여 도달 가능한지 체크
        boolean ans = bfs();

        // 도달 가능 시 1, 아니면 0 출력
        System.out.println(ans ? 1 : 0);
        br.close();
    }

    private static boolean bfs(){
        Queue<Integer> q = new LinkedList<>();

        // 7, 0 위치를 최초에 입력
        q.offer(56);

        while(!q.isEmpty()){
            int size = q.size();
            
            // 현재 이동 기준 방문 여부를 체크함.
            boolean visited[][] = new boolean[8][8];

            // 현재 Queue의 모든 내용을 모두 빼서 다음 위치를 찾는다.
            for(int i=0; i < size; i++){
                int p = q.poll();
                int y = p / 8;
                int x = p % 8;

                // 벽이 이동해서 현재 위치가 벽이 되었다면 더 이상 이동 불가
                if(map[y][x]) continue;

                // 목표 위치에 도달한 경우 true 반한
                if(y == 0) return true;

                // 벽이 0개 라면 true 반환
                if(wall.size() == 0) return true;

                // 갈 수 있는 9군데의 위치 모두 체크
                for(int j=0; j < 9; j++){
                    int ny = y + dy[j];
                    int nx = x + dx[j];

                    // 범위를 벗어난 경우는 제외
                    if(ny < 0 || ny >= 8 || nx < 0 || nx >= 8) continue;

                    // 벽의 위치가 아니고 다른 위치에 의해 이미 방문된 곳이 아니면 Queue에 삽입
                    if(!map[ny][nx] && !visited[ny][nx]){
                        q.offer(ny * 8 + nx);
                        visited[ny][nx] = true;
                    }
                }
            }
            // 벽이 남아 있는 경우, 벽을 1칸 씩 내린다.
            if(wall.size() > 0) reposition();
        }
        return false;
    }

    // 벽을 내리는 메소드
    private static void reposition(){
        Queue<Integer> subq = new LinkedList<>();

        // 현재의 모든 벽을 꺼내서 마지막 줄이 아니라면 +1씩 수행 한다.
        while(!wall.isEmpty()){
            int idx = wall.poll();
            int y = idx / 8;
            int x = idx % 8;

            // 우선 벽이 아니도록 표시
            map[y][x] = false;
            if(y < 7) {
                subq.offer((y+1) * 8 + x);
            }
        }

        // Subq에 다음에 벽이 될 위치가 들어있으므로 모두 꺼내서 wall로 만든다.
        while(!subq.isEmpty()){
            int idx = subq.poll();
            map[idx/8][idx%8] = true;
            wall.offer(idx);
        }
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.