[백준] 2178_미로탐색 / BFS, 최단경로보장

 

 

Sliver

 

 

문제

 

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

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

 

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

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

 

 

입력

 

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

 

 

출력

 

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

 

---

 

풀이_BFS

 

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

class Main {
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int N, M;
    
    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 int[N][M];
        visited = new boolean[N][M];

        for(int i=0; i<N; i++){
            String str = br.readLine();
            for(int j=0; j<M; j++){
                if(str.charAt(j) == '1') map[i][j] = 1;    
            }
        }

        visited[0][0] = true;
        bfs(0, 0);
        
        System.out.println(map[N-1][M-1]);
        br.close();
    }

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

        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {x, y});
        while(!q.isEmpty()){
            int[] newnode = q.poll();
            int qx = newnode[0];
            int qy = newnode[1];
            for(int i=0; i<4; i++){
                int xx = qx + dx[i];
                int yy = qy + dy[i];
                if(xx>=0 && xx<N && yy>=0 && yy<M && !visited[xx][yy] && map[xx][yy]!=0){
                    visited[xx][yy] = true;
                    map[xx][yy] = map[qx][qy] + 1;
                    q.offer(new int[] {xx, yy});
                }
            }
        }
        
    }
}

 

해결방법

• 입력받은 값을 map에 저장한다. 이 때 방문을 체크하기 위해 같은 크기의 boolean배열 visited를 생성한다. 
• 좌표가 {0, 0}인것부터 탐색을 시작한다. 
  • 현재 위치는 방문했으므로 visited를 true로 업데이트한다.
  • 현재 위치에서 상하좌우 4방향을 탐색하고,  값이 0이 아니고 방문한 적이 없을 경우 현재 위치를 이동시킨다.
  • 이동할 때마다 현재 칸의 값을 이전값 + 1 로 업데이트하고, 방문 배열도 업데이트한다 
    -> map[xx][yy] = map[qx][qy] + 1;
    -> visited[xx][yy] = true;
• Queue 빌 때까지 반복한다.
• 도착점에 저장된 값이 최단 경로를 나타내므로 이를 출력한다. map[N-1][M-1] 

 

미로찾기의 경우 DFS로는 문제를 통과할 수 없다. 

이는 BFS는 최단경로를 보장하지만 DFS는 최단경로를 보장하지 않기 때문이다. 

 

 

BFS와 DFS의 차이

• BFS :  너비를 우선으로 탐색하며, 시작점에서 가까운 좌표부터 차례대로 탐색하여 최단 경로를 보장한다. BFS는 경로를 하나씩 넓혀가며 가장 먼저 도착한 경로가 최단 경로이다.
• DFS : 깊이 우선 탐색으로, 한 경로를 끝까지 탐색한 후 다시 돌아와 다른 경로를 탐색하며 최단 경로를 보장하지 못할 수 있다.  DFS는 미로의 경로를 깊이 우선으로 탐색하면서 더 긴 경로를 먼저 탐색할 가능성이 크다.

 

 

---

https://www.acmicpc.net/problem/2178