Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
문제
https://www.acmicpc.net/problem/1238
1238번: 파티
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어
www.acmicpc.net
풀이
solved.ac 난이도: Gold 3
다익스트라를 두 번 적용해야 했던 문제.
다익스트라는 최단 경로 알고리즘 중에서 단일 시작점 알고리즘으로 하나의 시작점에서 다른 모든 점까지의 거리를 구한다.
하지만 문제에서는 파티가 진행되는 마을을 도착점으로 하고, 다른 모든 점에서 해당 점을 향해 최단 경로로 이동해야한다.
그렇다면, 반대로 파티 마을을 시작점으로 하고, 다른 모든 점으로의 최단 경로를 구하면 어떨까?
그래프의 모든 단 방향 간선들을 반대 방향으로 전환하면
다른 점들이 파티 마을로 향하는 최단 경로를 반대로, 파티 마을에서 다른 마을들로의 최단 경로를 구할 수 있다.
따라서, 단일 시작점 알고리즘인 다익스트라로 최단 경로를 구할 수 있다.
이렇게 구한 시작점(파티 마을)에서 각 점까지의 최단 경로를 departure_dist(출발 거리)라고 하자.
이제 파티가 끝나고 집으로 돌아갈 시간이다.
파티 마을에서 각 마을로의 최단 경로는 단일 시작점의 조건과 일치한다.
따라서 입력으로 받은 순방향 간선들을 그대로 이용하여 최단 거리를 계산해주자.
이렇게 구한 최단 거리를 arrival_dist(도착 거리)라고 하자.
이제 구해놓은 각 점의 departure_dist와 arrival_dist을 합하여
어느 마을이 파티 마을을 오고 가는데 가장 거리가 먼지 구할 수 있다.
코드
'알고리즘 공부 > 백준' 카테고리의 다른 글
| [백준] No.13308 - 주유소 (C++, 다익스트라) (0) | 2021.05.01 |
|---|---|
| [백준] No.1162 - 도로포장 (C++, 다익스트라) (1) | 2021.04.30 |
| [백준] No.2536 - 버스 갈아타기 (C++, BFS) (0) | 2021.04.25 |
| [백준] No.12851 - 숨바꼭질 2 (C++, BFS) (0) | 2021.04.22 |
| [백준] No.5214 - 환승 (C++, BFS, 더미 노드) (0) | 2021.04.21 |