알고리즘 풀이 - 백준 2178(미로 탐색, 그래프(BFS))

 

관련글

 

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

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

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

 

NxM크기의 미로가 주어질 때, 1은 이동 가능하고 0은 불가하다면 (1, 1) 에서 (N, M)으로 이동 시 지나야 하는 최소의 칸 수를 구하는 문제

 

 

2. 풀이

 

이 문제는 NxM 크기의 지도가 하나의 미로로 주어진다. (1, 1)에서 (Index라면 0, 0) 이동을 시작하여 주어진 값 (N, M)으로 이동해야 하되 최소로 이동하는 경우를 구한다.

그러므로 현재 위치에서 부터 탐색을 시작하여 각 위치를 최소로 이동할 수 있는 경우를 찾은 뒤 결국 마지막에 원하는 장소에 도달했을 때, 그 이동 횟수를 반환하면 된다.

 

이전 DFS, BFS 관련 포스팅에서도 설명했으나(상단 링크 참조) 최단 경로를 찾기 위해서는 BFS만 사용할 수 있다.

왜 그럴까? BFS는 시작점에서 모든 방문점을 최소 이동 경우의 수로 보장해주지만 DFS는 하나의 경로를 찾았을 때 해당 경로가 최소의 경로라는 것을 반드시 보장하지는 못하기 때문이다.

 

간단한 예시를 위해 아래의 그림을 보자.

 

만약 우리가 주황색으로 칠해진 곳에서 빨간색으로 칠해진 곳으로 가고자 한다고 할 때, 유일한 경로는 파란 화살표와 빨간 화살표가 있을 수 있다.(다른 것도 가능하지만 대표적으로)

 

그럼 BFS로 탐색을 하면 빨간 부분, 파란 부분 인접 정점을 동시에 차례 대로 탐색을 하게 되며 시작점이 고정이라서 무조건 모든 인접 정점이 최소의 경우로만 이동하도록 보장이 된다.

그래서 BFS로 탐색 시, 원하는 위치에 도달했다면 추가 탐색을 그만두어 빠르게 문제를 해결할 수 있게 된다.

 

그런데 DFS로 탐색을 하면, 상단의 빨간색 부분 부터 우선 탐색이 이루어질 수 있다. 하지만 이 경로는 최소 경로라는 보장이 불가능하다! 실제 위의 예시에서는 최소 경로가 아니다.

보장을 하기 위해서는 동일 위치에 도달할 수 있는 모든 경우를 체크해야 하는데, 그것은 DFS가 아니라 Brute Force 방법이 된다. 그러면 문제를 푸는데, 시간복잡도가 높아져 문제를 풀 수 없게 된다.

따라서 아래 문제는 BFS를 통해 탐색을 수행해보자.(Brute Force코드도 일단 넣어는 놓았다.)

 

 

3. 코드

 

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

 

① Brute Force 로 풀기 - 시간 초과 발생

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

public class Main{
    static int n;
    static int m;
    static String[] map;
    static boolean[][] visited;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, -1, 0, 1};
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new String[n];
        visited = new boolean[n][m];
        
        for(int i=0; i < n; i++){
            map[i] = br.readLine();
        }
        
        int ans = dfs(0, 0, 1);
        sb.append(ans);
        
        System.out.println(sb);
        br.close();
    }
    
    private static int dfs(int i, int j, int pass){
        if(i == n-1 && j == m-1) return pass;
        if(pass > ret) return Integer.MAX_VALUE;
        
        visited[i][j] = true;
        
        int ret = 10000;
        for(int k=0; k < 4; k++){
            int ny = i+dy[k];
            int nx = j+dx[k];
            
            if(ny < 0 || ny > n-1 || nx < 0 || nx > m-1 || visited[ny][nx] || map[ny].charAt(j) - '0' == 0) continue;
            
            ret = Math.min(dfs(ny, nx, pass+1), ret);
        }
        
        // 이 부분에 의해 방문이 이미 완료된 정점을 다시 미 방문 상태로 돌려놓게 되어
        // DFS가 아닌 Brute Force가 된다.
        visited[i][j] = false;
        return ret;
    }
}

 

② BFS로 풀기

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

public class Main{
    static int n;
    static int m;
    static String[] map;
    static int[][] min;
    static boolean[][] visited;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, -1, 0, 1};
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new String[n];
        min = new int[n][m];
        visited = new boolean[n][m];
        
        // 우선 map을 초기화하고 각 위치로의 최소 경로를 최대값으로 설정
        for(int i=0; i < n; i++){
            map[i] = br.readLine();
            Arrays.fill(min[i], Integer.MAX_VALUE);
        }
        
        // (0, 0) 에서 (n-1, m-1)까지 최단 경로를 BFS로 탐색
        bfs();
        
        sb.append(min[n-1][m-1]);  
        System.out.println(sb);
        br.close();
    }
    
    private static void bfs(){
        Queue<Map> q = new LinkedList<>();
        q.offer(new Map(0, 0));
        visited[0][0] = true;
        min[0][0] = 1;
        
        while(!q.isEmpty()){
            Map now = q.poll();
            
            int y = now.y;
            int x = now.x;
            for(int k=0; k < 4; k++){
                int ny = y + dy[k];
                int nx = x + dx[k];
                
                // 다음 탐색 위치가 범위 안에 있고 미방문 상태이며 갈 수 있는 경로이면
                if(0 <= ny && ny < n && 0 <= nx && nx < m && !visited[ny][nx] && map[ny].charAt(nx) == '1'){
                    min[ny][nx] = min[y][x] + 1;
                    visited[ny][nx] = true;
                    q.offer(new Map(ny, nx));
                }
            }
        }
    }
}

// 다른 class를 만들어서 위치 값을 저장하여 queue에 저장
class Map{
    int y;
    int x;
    public Map(int y, int x){
        this.y=y;
        this.x=x;
    }
}

 

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