[백준] 1948 임계 도로

1948번: 임계경로

 

boj.kr

풀이

이 문제는 위상 정렬과 BFS를 사용해서 해결했다. 우선 위상 정렬을 사용하면 도착 도시까지 걸리는 최대 시간을 쉽게 구할 수 있다. 그리고 나면 관건은 1분도 쉬지 않고 달려야 하는 도로를 세는 것이다. 이는 위상 정렬을 했던 결과를 이용해서 구할 수 있다. 위상 정렬을 수행해서 각 도시까지 도착하는데 걸리는 최대 시간을 알아냈기 때문에 이번에는 도착지에서 출발지로 역행하면서 탐색해준다.

어떻게 도로의 개수를 찾을 수 있는지는 그림을 보면서 이해하자.

위의 그림처럼 1번 도시까지의 최대 시간이 7, 2번 도시까지의 최대 시간이 17이고 1번 도시와 2번 도시 사이의 도로를 건너는데는 10분이 걸린다고 가정하자. 그렇다면 2번 도시에서 1번 도시로 탐색을 할 때 2번 도시까지 걸린 시간 - 1~2 도로를 건너는데 걸리는 시간 = 1번 도시까지 걸린 시간이면 해당 도로를 건널 때 1분도 쉬지 않고 건넌 것이 된다.

이러한 방식으로 도로의 개수를 세어주면 문제를 해결할 수 있다. 도로 개수를 쉽게 셀 수 있게 하기 위해서 역방향 인접 리스트를 생성했다.

코드

C++