[백준] 2178번 : 미로 탐색

문제

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

 

위와 같은 미로가 주어졌을 때 도착지까지 갈 수 있는

최단 경로를 구하는 문제

 

접근 방식

기존 BFS 알고리즘으로 문제를 풀 때는 방문 여부만 기록했다면

이제는 방문 여부와 출발지로부터의 거리도 기록해주면 된다.

 

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

 

도착지를 처음 방문 했을 때가 가장 빠른 최단 경로일테니

출발지에서 도착지까지의 거리를 출력해주면 된다.

 

조심해야 할건 같은 지점에서 갈 수 있는 경로의 거리는

서로 같아야 한다.

 

1	0	9	10	11	13
2	0	8	0	14	0
3	0	7	0	15	16
4	5	6	0	17	18

 

이런식으로 되면 잘못된 결과가 나오게 된다.

 

풀이

public class Main {
	static int[] dx = {1, 0, -1, 0};
	static int[] dy = {0, 1, 0, -1};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		int[][] maze = new int[n][m];
		boolean[][] isVisited = new boolean[n][m];

		for (int i = 0; i < n; i++) {
			String[] input = br.readLine().split("");

			for (int j = 0; j < m; j++) {
				maze[i][j] = Integer.parseInt(input[j]);
			}
		}

		Queue<Pair> queue = new ArrayDeque<>();

		isVisited[0][0] = true;
		queue.offer(new Pair(0, 0, 1));

		while (!queue.isEmpty()) {
			Pair cur = queue.poll();

			if (cur.x == n - 1 && cur.y == m - 1) {
				System.out.println(cur.distance);
				break;
			}

			for (int dir = 0; dir < 4; dir++) {
				int nx = cur.x + dx[dir];
				int ny = cur.y + dy[dir];

				if (nx < 0 || nx >= n || ny < 0 || ny >= m)
					continue;
				if (maze[nx][ny] == 0 || isVisited[nx][ny])
					continue;

				isVisited[nx][ny] = true;
				queue.offer(new Pair(nx, ny, cur.distance + 1));
			}
		}
	}

	private static class Pair {
		int x;
		int y;
		int distance;

		public Pair(int x, int y, int distance) {
			this.x = x;
			this.y = y;
			this.distance = distance;
		}
	}
}