[ Baekjoon ] 2178번 - 미로 탐색

2178번: 미로 탐색

 

풀이 방법

맨 처음 풀었을 때 런타임 에러(StackOverflow)가 났다. 그 이유는 잘못된 재귀호출이 반복되어서였다. 일반적인 BFS가 아니라 나만의 이상한 BFS로 Stack과 Queue를 섞어 만들었기 때문이다. 그래서 Queue만 사용하는 BFS로 구현하였다.

이때, 최단 경로를 찾아야 하기 때문에 BFS 탐색을 해주었다.

 

구현 코드

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 Q_2178 {
	static int N, M;
	static int[][] array, visited;
	static Queue<int[]> queue = new LinkedList<int[]>();
	static int[] x = { -1, 1, 0, 0 };
	static int[] y = { 0, 0, -1, 1 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		array = new int[N+1][M+1];
		String line;
		for (int i = 1; i <= N; i++) {
			line = br.readLine();
			for (int j = 1; j <= M; j++) {
				array[i][j] = Character.getNumericValue(line.charAt(j-1));
			}
		}
		
		visited = new int[N+1][M+1];
		BFS(1,1);
		
		System.out.print(array[N][M]);
	}
	
	static void BFS(int i, int j) {
		visited[i][j] = 1;
		queue.offer(new int[] {i, j});
		
		while (!queue.isEmpty()) {
			int[] map = queue.poll();
			
			for (int k = 0; k < 4; k ++) {
				if (map[0] + x[k] > 0 && map[0] + x[k] <= N && map[1] + y[k] > 0 && map[1] + y[k] <= M)
					if (array[map[0]+x[k]][map[1]+y[k]] == 1 && visited[map[0]+x[k]][map[1]+y[k]] == 0) {
						queue.add(new int[] {map[0] + x[k], map[1] + y[k]});
						visited[map[0] + x[k]][map[1] + y[k]] = 1;
						array[map[0]+x[k]][map[1]+y[k]] = array[map[0]][map[1]] + 1; // 이 부분이 핵심
					}
				
			}
		}
	}
}