[BOJ] 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)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

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

출력

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

예제 입력 1 

4 6

101111

101010

101011

111011

예제 출력 1 

15

예제 입력 2 

4 6

110110

110110

111111

111101

예제 출력 2 

9

예제 입력 3 

2 25

1011101110111011101110111

1110111011101110111011101

예제 출력 3

38

예제 입력 4 

7 7

1011111

1110001

1000001

1000001

1000001

1000001

1111111

예제 출력 4 

13

 

---

[문제 풀이]

모든 경로의 탐색이 아니라 지나야 하는 최소의 칸 수를 출력해야함을 놓쳐서 한 번에 문제를 통과할 수 없었다.

지나야 하는 최소의 칸 수를 계산하기 위해 2차원 정수 배열 dist를 선언하였고 각 칸까지 이동해야하는 칸 수를 해당 배열에 저장하였다. 

좌표를 이동할 수 있는 범위는 상, 하, 좌, 우 이므로 dx, dy배열을

static int[] dx = {-1, 1, 0, 0}; static int[] dy = { 0, 0, -1, 1}; 와 같이 만들었다.

방문한 노드는 queue에 넣어 bfs로 미로를 탐색하도록 하였다.

queue에 원소가 없을 때까지, 또는 (N,M) 좌표에 도달할 때까지 반복문을 통해 미로를 탐색한다.

좌표를 상, 하, 좌, 우로 움직이며 해당 좌표의 값이 1인지, 그리고 해당 좌표를 아직 방문하지 않았는지 여부를 파악해 해당 좌표 값이 1이며 아직 방문하지 않았으면 queue에 해당 좌표를 넣고, visit배열의 값을 true로 바꿔준다. 그 다음 현재 노드에서 다음 노드로 이동한 경우를 의미하는 것이므로 dist배열의 다음 노드의 값에 현재 노드의 dist 값 +1 을 넣어준다.

반복문이 종료되고 나면 dist[N-1][M-1]을 출력한다.

[코드]

import java.util.*;
class Node{
   int row;
   int col;

   public Node(int row, int col) {
     this.row = row;
     this.col = col;
   }
}
public class Main{
   static int[][] maze;
   static boolean[][] visit;
   static Queue<Node> queue = new LinkedList<>(); 
   static int[] dx = {-1, 1, 0, 0};
   static int[] dy = { 0, 0, -1, 1};
   static int[][] dist;

    public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         int N = sc.nextInt();
         int M = sc.nextInt();
         maze = new int[N][M];
         visit = new boolean[N][M];
         dist = new int[N][M];
       
         for(int i=0;i<N;i++) {
          String str = sc.next();
          for(int j=0;j<M;j++)
          maze[i][j] = str.charAt(j)-'0';
         }
         
         queue.add(new Node(0,0));
         visit[0][0] =true;
         dist[0][0] = 1;
         while(!queue.isEmpty()) {
           Node node = queue.poll();
 
           if (node.row == N - 1 && node.col == M - 1)
             break;
 
 
           for(int i=0;i<4;i++) {
               int nx = node.row + dx[i];
               int ny = node.col + dy[i];
 
              if(nx>=0 && ny>=0 && nx<N && ny<M) {
                  if(maze[nx][ny]==1 && !visit[nx][ny]) {
                    visit[nx][ny] = true;
                    queue.add(new Node(nx, ny));
                    dist[nx][ny] = dist[node.row][node.col]+1;
 
                   }
                }
            }
         }
         
         System.out.println(dist[N-1][M-1]);
    }
}