[이.코.테] Chapter 05 DFS/BFS - 미로 탈출 (Java)

미로 탈출 문제 (교재 152p)

난이도 ●◐○ | 풀이 시간 30분 | 시간 제한 1초 | 메모리 제한 128MB

 

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

 

입출력 조건)

입력 조건	- 첫째 줄에 두 정수 N, M (4 ≤ N, M ≤ 200)이 주어진다.   다음 N개의 줄에는 각각 M개의 정수 (0 혹은 1)로 미로의 정보가 주어진다.   각각의 수들은 공백없이 붙어서 입력으로 제시된다.   또한 시작 칸과 마지막 칸은 항상 1이다.
출력 조건	- 첫째 줄에 최소 이동 칸의 개수를 출력한다.

입출력 예시)

입력 예시	출력 예시
5 6 101010 111111 000001 111111 111111	10

---

문제 풀이 방법

• BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문에, 이 문제는 BFS를 이용했을 때 효과적이다.
• 시작지점(1,1)에서부터 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣는다.
• 특정한 노드를 방문하면 그 이전 노드의 거리에 1을 더한 값을 배열에 넣는다.

 

소스 코드

package exam05_dfs_bfs;
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Q2_Escase_Maze {
    public static int n, m;
    public static int[][] graph;
    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};
    public static Queue<Pair> q = new LinkedList<>();

    public static int bfs(int x, int y){
        q.add(new Pair(x,y));

        // 큐가 빌 때까지 반복
        while(!q.isEmpty()){
            Pair cur = q.poll();
            x = cur.x;
            y = cur.y;

            // 현재 위치에서 네 방향으로의 위치 확인
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                // 미로 찾기 공간을 벗어난 경우 무시
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                // 괴물인 경우 무시
                if (graph[nx][ny] == 0) continue;
                // 괴물이 없고, 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
                if (graph[nx][ny] == 1){
                    graph[nx][ny] = graph[x][y] + 1;
                    q.add(new Pair(nx, ny));
                }

            }
        }

        // 가장 오른쪽 아래까지의 최단 거리 반환
        return graph[n-1][m-1];

    }


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

        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        graph = new int[n][m]; // 미로

        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0; j < m; j++) {
                graph[i][j] = str.charAt(j) - '0';
            }
        }

        System.out.println(bfs(0,0));

        br.close();
        bw.close();
    }

    public static class Pair {
        int x;
        int y;

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