문제 정리

---

미로를 탈출할 수 있는 최소한의 이동 칸 수를 구해야 한다

입력

행 크기 열 크기
맵 정보

출력

최소한의 이동 칸 수

idea 정리

---

dfs, bfs를 모두 적용할 수 있는 문제다
하지만 입력값의 크기가 행, 열의 크기가 100까지라서
배열의 크기가 10,000까지 될 수 있어서 dfs로 하면 시간초과가 난다
어떻게 아냐면 dfs로 먼저 풀어봤기 때문이다..

bfs이던지 dfs이던지 다른 조건 추가 없이 탐색을 정확히 구현하면 되지만
dfs는 시간초과이니 bfs로 구현한다

알고리즘 구성

---

1. 배열을 입력 받는다
2. (1, 1)을 기준으로 bfs를 돌면서 너비의 깊이를 센다
3. 너비 깊이 출력

구현

---

//미로 탐색
public class Main {
	static class Point {
		int r, c, value;

		public Point(int r, int c, int value) {
			super();
			this.r = r;
			this.c = c;
			this.value = value;
		}
	}

	static int N, M, res = 0;
	static Point[][] map;
	static boolean[][] visited;

	static int[] dr = { -1, 0, 1, 0 }; // 상우하좌
	static int[] dc = { 0, 1, 0, -1 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new Point[N + 1][M + 1];
		visited = new boolean[N + 1][M + 1];

		for (int i = 1; i <= N; i++) { // 맵 입력
			char[] input = br.readLine().toCharArray();
			for (int j = 1; j <= M; j++) {
				int c = input[j - 1] - '0';
				map[i][j] = new Point(i, j, c);
			}
		}
		visited[1][1] = true;
		bfs(1, 1);
		bw.write(res + "");
		bw.flush();
		bw.close();
		br.close();
	}

	static void bfs(int r, int c) {
		Queue<Point> q = new LinkedList<>();
		q.add(map[r][c]);

		while (!q.isEmpty()) {
			res++;		//레벨 탐색 끝
			int size = q.size();
			for (int i = 0; i < size; i++) {
				Point now = q.poll();
				if(now.r==N && now.c==M) {
					return;
				}
				for (int j = 0; j < 4; j++) {
					int nr = now.r + dr[j];
					int nc = now.c + dc[j];

					if (1 <= nr && nr <= N && 1 <= nc && nc <= M && map[nr][nc].value == 1) {
						if (visited[nr][nc] || map[nr][nc].value == 0) continue;
							q.add(map[nr][nc]);
							visited[nr][nc] = true;
					}
				}
			}
		} // end of while
	}
}

결과

---