[DFS/BFS] 미로 탈출

문제

N x M 크기의 직사각형 형태의 미로가 있다. 미로에는 벽이 있어 이를 피해 탈출해야 한다. 출발 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하며 한번에 한 칸씩 이동할 수 있다. 이때 벽이 있는 부분은 0으로, 벽이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

 

입력 조건

• 첫째 줄에 두 정수 N, M(4 <= N,M <= 200)이 주어집니다. 다음 N개의 줄에는 각각 M개의 정수(0 or 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이 붙어서 입력으로 제신된다. 또한 시작 칸과 마지막 칸은 항상 1이다.

출력 조건

• 첫째 줄에 최소 이동 칸의 개수를 출력한다.

입력 예시

5 6
101010
111111
000001
111111
111111

 

출력 예시

10

---

아이디어

대부분의 문제 중, 최소 라는 말이 들어가면 BFS를 떠올리면 된다. (최소 이동 횟수, 최단거리, 등)

이 문제에서도 최소 칸의 개수를 구하는 것이므로 최단거리 문제와 동일하다. 시작점의 좌표 (1, 1) -> 끝점 (N, M) 까지의 최단거리를 구하면 된다.

 

좌표 점을 표시하기 위해 Pos 클래스를 생성한다. (처음에는 이를 생성하지 않고, new Integer[] {int x, int y} 형태로 작성했으나, 이렇게 하면 x, y좌표가 초기 점으로 고정되니 앞으로는 생각해서 작성하자)

static class Pos {
    int x, y;
    Pos(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

 

앞선 구현 문제와 마찬가지로, 좌표 문제는 보통 dx, dy 배열을 만들어 방향을 정하는 것이 도움된다. 

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

 

N, M, 그래프를 설정한다.

// N x M 입력
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());

// 그래프 설정
graph = new int[N+1][M+1];
for(int i=1; i<=N; i++) {
    String line = br.readLine();
    for(int j=1; j<=M; j++) {
        graph[i][j] = line.charAt(j-1) - '0';
    }
}

 

이 문제에서의 BFS 동작 방식은 다음과 같다.

1. 초기 위치로부터 BFS 탐색 (1, 1)
2. 큐에 초기 위치 add
3. 큐에서 한점을 poll 하고, 그 점에 대해 상,하,좌,우 네 방향 탐색
4. 해당 점이 1이라면(처음 방문한다면) 현재 위치의 값 + 1 하고, 큐에 추가
5. 3 ~ 4번 과정 큐가 빌때까지 반복

private static int BFS(int x, int y) {
    Queue<Pos> q = new LinkedList<>();
    q.add(new Pos(x, y));

    while(!q.isEmpty()) {
        Pos cur = q.poll();
        for(int i=0; i<4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            // 범위 벗어나면 무시
            if(nx < 1 || ny < 1 || nx > N || ny > M) continue;
            // 괴물인 경우 무시
            if(graph[nx][ny] == 0) continue;
            // 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
            if(graph[nx][ny] == 1) {
                graph[nx][ny] = graph[cur.x][cur.y] + 1;
                q.add(new Pos(nx, ny));
            }
        }
    }
    return graph[N][M];
}

 

점의 위치를 기반으로 BFS 탐색을 이어나가는 것을 기억하자.