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

 

 

 

 

1. 두 정수 N과 M의 크기가 100으로 매우 작기 때문에, 시간 제한은 별도로 고려하지 않아도 됨.

 

 

2. 문제에서 요구하는 것은, (1,1)을 출발지점으로 시작해서, (N,M)까지 도달하기 위해 지나야 하는 칸 수의 최솟값을 구하는 것임 

 

 

너비 우선 탐색방법(BFS)과 깊이 우선 탐색(DFS)중에,  너비 우선 탐색방법이 해당 깊이에서 갈 수 있는 노드 탐색을 마친 후 다음 깊이로 넘어가기 때문에, 이 문제는 너비 우선 탐색 방법을 써야함.

 

 

 

 

(N-1,M-1)까지 도달하기까지 거리를 점진적으로 ++하며, 마지막 지점에 도달했을경우의 배열 값을 출력하면됨

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
	static int[] dx = { 0, 1, 0, -1 }; 
	static int[] dy = { 1, 0, -1, 0 };
	static boolean[][] visited;
	static int[][] A;
	static int N, M;  
	
	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());
		A = new int[N][M];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			String line = st.nextToken();
			for(int j=0; j<M; j++) {
				A[i][j] = Integer.parseInt(line.substring(j,j+1));
			}
		}
		visited = new boolean[N][M];
		BFS(0,0); // 시작 지점
		System.out.println(A[N-1][M-1]);
	}
	
	public static void BFS(int i, int j) {
		Queue<int []> queue = new LinkedList<>();
		queue.offer(new int[] {i,j});
		visited[i][j] = true;
		while(!queue.isEmpty()) {
			int now[] = queue.poll();
		    for (int k=0; k<4; k++) {
		    	int x = now[0] + dx[k];
		    	int y = now[1] + dy[k];
		    	// 좌표 유효성 검사하기
		    	if(x>=0 && y>=0 && x<N && y<M)
		    	{
		    		//이미 방문하지 않았고, 갈수 있다면 방문 Check, 깊이 업데이트하기
		    		if(A[x][y] != 0 && !visited[x][y]) {
		    			visited[x][y] = true;
		    			A[x][y] = A[now[0]][now[1]] + 1; // 깊이 업데이트하기
		    			queue.add(new int[] {x,y });
		    		 }
		    	 }
		    }
		    }	
	      }
 }

 

          

1	0	9	10	11	12
2	0	8	0	12	0
3	0	7	0	13	14
4	5	6	0	14	15