[백준 / BOJ] 14940번 : 쉬운 최단거리 (JAVA)

https://www.acmicpc.net/problem/14940

14940번: 쉬운 최단거리

제목 그대로 정석 최단거리 구하기인데 문제 조건을 빠뜨리기 쉬워 한 번 틀렸습니다 를 받았다.

 

최단 거리 구하기

Queue를 사용한 BFS로 구현 가능하다. 시작은 입력값이 2인 위치부터이고, 도달하는 데에 걸린 시간을 추가해서 돌려주면 된다.

 

방문 체크와 시간을 동시에 확인하고 싶어서 cost라는 배열을 만들었다. 처음 입력값을 받으면서 cost의 원소 값을 모두 -1로 초기화해주었다(도달할 수 없는 곳은 -1로 출력하기 때문에). 그리고 BFS를 돌리는 동안 cost의 원소값이 -1인 경우만 방문을 허락했다.

 

여기서 중요한 점은 방문을 할 수 없는 두 가지 경우가 있다는 것이다.

 

1) 처음부터 방문이 안되는 경우(입력값 0인 경우)

2) 방문 가능한 곳이지만, 갈 수 있는 경로가 없는 경우(입력값 1이지만 갈 수 없는 경우)

 

처음에는 BFS를 돌리면서 map[nr][nc]가 0이면 cost[nr][nc]는 0이고 que에 다음 원소를 넣지 않도록 했는데, 이렇게 구현하는 경우에는 다음 반례에서 틀리게 된다.

// 입력
2 2
2 0
0 0

// 출력값
2 0
0 -1

// 정답
2 0
0 0

(1, 1)은 원래 갈 수 없는 곳인데, BFS가 닿지 않아서 0이 아니라 -1로 출력되는 것이다.

 

이에 애초에 map 입력을 받을 때, 값이 2인 것과 같이 값이 0인 경우에도 cost를 0으로 두도록 변경했고, 정답 처리를 받을 수 있었다.

 

전체 코드

public class Main {

	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[][] map = new int[N][M];
		
		Queue<int[]> que = new LinkedList<>();
		int[][] cost = new int[N][M];
		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			Arrays.fill(cost[i], -1);
			for (int j = 0; j < M; j++) {
				map[i][j] = str.charAt(j * 2) - '0';
				if(map[i][j] == 2) {
					que.offer(new int[] {i, j, 0});
					cost[i][j] = 0;
				} else if(map[i][j] == 0) {
					cost[i][j] = 0;
				}
			}
		}
		
		int[] dr = {-1, 0, 1, 0};
		int[] dc = {0, -1, 0, 1};
		
		while(!que.isEmpty()) {
			int[] cur = que.poll();
			
			for (int d = 0; d < 4; d++) {
				int nr = cur[0] + dr[d];
				int nc = cur[1] + dc[d];
				
				if(nr >= N || nc >= M || nr < 0 || nc < 0) continue;
				if(cost[nr][nc] != -1) continue;
				
				que.offer(new int[] {nr, nc, cur[2] + 1});
				cost[nr][nc] = cur[2] + 1;
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				sb.append(cost[i][j]).append(" ");
			}
			sb.append("\n");
		}
		System.out.print(sb);
	}

}