백준 2178 미로 탐색 (Java)

1. 문제 링크

2178번: 미로 탐색

 

2. 문제 및 입출력예제

 

3. 문제 풀이

bfs 탐색 방식으로 문제를 풀었다.

최소 칸을 구해야 하기 때문에 큐의 크기를 구해 한 번의 횟수에 갈 수 있는만큼만 큐에서 빼서 처리했다.

미로의 끝에 도달한다면 종료한다.

 

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.io.IOException;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int N = Integer.parseInt(split[0]);
		int M = Integer.parseInt(split[1]);
		boolean[][] map = new boolean[N+1][M+1];
		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+1][j+1] = true;
				}
				else {
					map[i+1][j+1] = false;
				}
			}
		}
		
		int[] dx = {0,0,-1,1};
		int[] dy = {-1,1,0,0};
		
		Queue<int[]> queue = new ArrayDeque<>();
		queue.offer(new int[] {1, 1});
		map[1][1] = false;
		
		int result = 1;
		out:
		while(!queue.isEmpty()) {
			int size = queue.size();
			for(int i=0;i<size;i++) {
				int[] now = queue.poll();
				int x = now[0];
				int y = now[1];
				if(x==N && y==M) {
					break out;
				}
				
				for(int d=0;d<4;d++) {
					int X = x+dx[d];
					int Y = y+dy[d];
					if(X<1 || X>N || Y<1 || Y>M || !map[X][Y]) {
						continue;
					}
					queue.offer(new int[] {X, Y});
					map[X][Y] = false;
				}
			}
			result++;
		}
		System.out.println(result);
	}

}