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

 

 

 

 

 

문제

 

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

 

 

 

 

입력 조건

 

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

 

출력 조건

 

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

 

풀이 과정

 

최단거리를 구하는 문제로 전형적인 bfs 문제이다. 해당 문제에서는 탐색이 실패할 경우가 없다고 가정하고 있다. 따라서 queue가  빌 때까지 인접 노드가 1인 경우에 인접 노드를 이전 노드의 깊이 값 + 1으로 갱신하면서 queue를 삽입하면 된다. 만약 최단 경로를 처음 푸는 분이라면 이 알고리즘이 어떻게 최단 경로만을 구해내는지, 탐색이 실패할 경우가 있다면 어떻게 해야 할지 고민해보면 좋을 것 같다.

 

 

 

 

Java 코드

 

import java.util.*;
import java.io.*;

public class Main {

    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> queue = new LinkedList<>();

    public static class Pair {
        int x;
        int y;

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

    public static int bfs(int x, int y) {

        queue.add(new Pair(x, y));

        while (!queue.isEmpty()) {

            Pair pair = queue.poll();
            x = pair.x;
            y = pair.y;

            for (int i = 0; i < 4; i++) {
                int next_x = x + dx[i];
                int next_y = y + dy[i];

                if (next_x < 0 || next_y < 0 || next_x >= n || next_y >= m)
                    continue;

                if (graph[next_x][next_y] == 1) {
                    graph[next_x][next_y] = graph[x][y] + 1;
                    queue.add(new Pair(next_x, next_y));
                }
            }
        }

        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';
            }
        }

        bw.write(String.valueOf(bfs(0, 0)));

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