[백준] 2178번 미로탐색 BFS 탐색으로 풀기 (DFS로는 풀 수 없는 이유?) : Programming Story

1. 문제

1) 링크

www.acmicpc.net/problem/2178

2) 문제

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

3) 입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

4) 출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

더 자세한 문제의 사항을 보려면 위의 링크로 들어가보자.

2. 풀이

대부분의 그래프 문제는 BFS, DFS 두 방법으로 모두 가능하다. 하지만 이 문제는 DFS로는 풀 수 없고, BFS로밖에 푸 수 없다는 점에서 특이한 문제이다.

이는 왜냐하면 DFS의 경우 가능한 경우를 찾으면 되는 것이지 가장 빠른 길을 구하는 것이 아니기 때문이다. BFS의 경우에는 매 단계마다 가능한 경우를 탐색하기 때문에 (N,M)에 도달할 때까지 단계별로 시도해볼 수 있는 것이기 때문이다.

따라서 이 문제는 BFS로 풀면서 모든 칸의 거리를 저장해 놓을 배열이 필요하다.

이 문제의 준비 배열

1. int [][] distance=new int[n][m];
//각 칸마다 거리를 저장해 놓을 배열이 필요함
2. boolean [][]check=new boolean [n][m];
// BFS를 하면서 이미 사용된 칸인지 체크. 사용되었으면 해당 칸을 true로 바꾸어놓음
3. Queue<Pair> queue=new LinkedList<>();
//BFS를 하기 위해 필요한 queue.

4. class Pair
//x행, y열을 기록하기 위해서 Pair라는 객체가 필요함. 이를 위해 class를 만들었음

각 칸마다 이 문제는 위, 아래, 좌, 우를 살펴보면서 해당칸이 사용이 되지 않았고 문제에서 입력받은 해당 칸의 숫자가 1이면 해당 칸의 거리를 1 증가하여 distance배열에 저장한다.

이것을 코드화시켜서 BFS 부분만 살펴보자.

 Queue<Pair> queue=new LinkedList<>();
        queue.add(new Pair(0,0));
        check[0][0]=true;
        distance[0][0]=1;
        while(!queue.isEmpty()){
            Pair p=queue.remove();
            int x=p.x;
            int y=p.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<n){
                    if (check[nx][ny]==false && a[nx][ny]==1){
                        queue.add(new Pair(nx, ny));
                        distance[nx][ny]=distance[x][y]+1;
                        check[nx][ny]=true;
                    }
                }
            }
        }

처음에 (1,1) 자리의 Pair를 queue에다가 넣은 뒤 시작해준다. 여기서는 배열이기 때문에 [0][0] 이 (1,1)을 의미한다.

이 문제도 저번에 다루었던,

https://www.programmingstory.com/2024/02/2667.html

위의 문제와 유사하나 이 문제는 BFS로밖에 풀 수 없다는 것이 특징이다. 만약 DFS로 푸는 것이 궁금하다면 위의 포스팅에서는 DFS로 푼 코드를 첨부했으니 살펴보자.

3. 코드

최종적으로 전체 코드를 살펴보면 아래와 같다.

import java.util.*;
class Pair{
    int x,y;
    Pair(int x, int y){
        this.x=x;
        this.y=y;
    }
}
public class Main{
    public static final int dx[]={0,0,1,-1};
    public static final int dy[]={1,-1,0,0};
    public static void main (String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int a[][]=new int[n][m];
        for(int i=0; i<n; i++){
            String s=sc.next();
            for(int j=0; j<m; j++){
              a[i][j]=s.charAt(j)-'0';
            }
        }
        int [][] distance=new int[n][m];
        boolean [][]check=new boolean [n][m];
        Queue<Pair> queue=new LinkedList<>();
        queue.add(new Pair(0,0));
        check[0][0]=true;
        distance[0][0]=1;
        while(!queue.isEmpty()){
            Pair p=queue.remove();
            int x=p.x;
            int y=p.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){
                    if (check[nx][ny]==false && a[nx][ny]==1){
                        queue.add(new Pair(nx, ny));
                        distance[nx][ny]=distance[x][y]+1;
                        check[nx][ny]=true;
                    }
                }
            }
        }
        System.out.println(distance[n-1][m-1]);
    }
    
}