[DFS/BFS] 백준 2178번 미로 탐색(Java)

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

2178번: 미로 탐색

📚 문제

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)의 위치로 이동할 수 있다.

칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

 

예제 입력	예제 출력
4 6 101111 101010 101011 111011	15

 

📝 문제 해결

BFS는 시작 지점에서 가까운 노드부터 차례대로 탐색하는 알고리즘으로 최단경로 문제를 풀 때 효과적이다.

1. 탐색 시작 노드를 큐에 삽입해준다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문가능(1)하나 아직 방문하지않은 노드가 있다면 큐에 삽입해주고 그 이전 노드의 거리에 1을 더해준다.
3. 큐에 더 이상 탐색할 노드가 없을 때까지 반복해준다.

 

💻 코드

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

public class BOJ2178 {
    static int N, M;
    static int[][] graph = new int[100][100];
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    
    public static int bfs(int x, int y){
        Queue<Point> que = new LinkedList<>();
        que.offer(new Point(x,y));
        
        while(!que.isEmpty()){
            Point p = que.poll();
            x = p.x;
            y = p.y;
            
            for(int i=0; i<4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if(nx>=0 && nx<N && ny>=0 && ny<M && graph[nx][ny]==1){
                    graph[nx][ny] = graph[x][y]+1;
                    que.offer(new Point(nx,ny));
                } 
            }
        }
        return graph[N-1][M-1];
    }
    
    public static void main(String[] args) throws IOException{
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      
      N = Integer.parseInt(st.nextToken());
      M = Integer.parseInt(st.nextToken());
        
      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));
    }
}