문제
[문제]
(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다.
너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것,
그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다.
그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익)
어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다.
다행히도 당신은 후각이 개만큼 뛰어나다.
이 후각으로 그들이 g와 h 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈다.
이 듀오는 대체 어디로 가고 있는 것일까?
[입력]
첫 번째 줄에는 테스트 케이스의 T(1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스마다
- 첫 번째 줄에 3개의 정수 n, m, t (2 ≤ n ≤ 2 000, 1 ≤ m ≤ 50 000 and 1 ≤ t ≤ 100)가 주어진다. 각각 교차로, 도로, 목적지 후보의 개수이다.
- 두 번째 줄에 3개의 정수 s, g, h (1 ≤ s, g, h ≤ n)가 주어진다. s는 예술가들의 출발지이고, g, h는 문제 설명에 나와 있다. (g ≠ h)
- 그 다음 m개의 각 줄마다 3개의 정수 a, b, d (1 ≤ a < b ≤ n and 1 ≤ d ≤ 1 000)가 주어진다. a와 b 사이에 길이 d의 양방향 도로가 있다는 뜻이다.
- 그 다음 t개의 각 줄마다 정수 x가 주어지는데, t개의 목적지 후보들을 의미한다. 이 t개의 지점들은 서로 다른 위치이며 모두 s와 같지 않다.
교차로 사이에는 도로가 많아봐야 1개이다. m개의 줄 중에서 g와 h 사이의 도로를 나타낸 것이 존재한다. 또한 이 도로는 목적지 후보들 중 적어도 1개로 향하는 최단 경로의 일부이다.
[출력]
테스트 케이스마다
- 입력에서 주어진 목적지 후보들 중 불가능한 경우들을 제외한 목적지들을 공백으로 분리시킨 오름차순의 정수들로 출력한다.아이디어
시간 초과를 해결할 방법이 잘 떠오르지 않아서 다른 분들의 블로그를 참고했다. (참고 사이트 부분에 기재)
문제 해석
지문을 요약하자면
출발점s에서 후보 목적지들까지의 최단 경로를 구하는데, 후보 목적지까지의 최단 경로에 g-h 사이의 간선이 포함되는 경우 도달 가능한 목적지라고 보고 출력하는 문제이다.
풀이 과정
-
후보 목적지 중 하나를
target이라고 한다. -
g와h사이의 거리를GH라고 한다. (양방향 그래프이므로g -> h=h -> g=GH) -
g와h사이의 거리를 지나는s➡️target경로는 아래와 같이 생각할 수 있다.- case 1️⃣: s ➡️ g ➡️ h ➡️ target
- case 2️⃣: s ➡️ h ➡️ g ➡️ target
-
⭐️
s➡️target최단거리는 아래와 같이 생각할 수 있다.- case 1️⃣: 최단거리(s ➡️ g) +
GH+ 최단거리(h ➡️ target) - case 2️⃣: 최단거리(s ➡️ h) +
GH+ 최단거리(g ➡️ target) - 만약 최단거리(s ➡️ target) == min(case 1️⃣, case 2️⃣)라면
target까지의 최단거리에g와h사이의 거리가 포함된다. (가능한 후보 목적지) - 만약 최단거리(s ➡️ target) != min(case 1️⃣, case 2️⃣)라면
target까지의 최단거리에g와h사이의 거리가 포함되지 않는다. (불가능한 후보 목적지)
- case 1️⃣: 최단거리(s ➡️ g) +
-
우리가 구해야하는 것은
s에서g, h, target까지의 최단거리g에서target까지의 최단거리h에서target까지의 최단거리
-
어떤 지점을 출발점으로, 다른 모든 지점까지의 최단거리는 다익스트라 알고리즘으로 구할 수 있다.
-
이때, 매
target마다 다익스트라 알고리즘을 수행할 필요 없이, 테스트케이스마다 3번만 다익스트라 알고리즘을 돌려주면 된다.s를 출발점으로 한 다익스트라 알고리즘의 결과g를 출발점으로 한 다익스트라 알고리즘의 결과h를 출발점으로 한 다익스트라 알고리즘의 결과
시간 복잡도
- 우선순위 큐를 사용한 다익스트라 알고리즘의 시간복잡도는 O(ElogV)
- 결과적으로 전체 시간복잡도는 O(T*3ElogV)로 시간초과를 피할 수 있다.
(매target(후보 목적지)마다 수행한다고 생각했으면 O(T t 3ElogV)로 시간초과)
제출 코드
구현 시 유의사항
-
다익스트라 알고리즘 수행 시, 모든 최단거리를
INF로 초기화한다. -
도달할 수 없는 정점은 계속
INF로 남아있게 된다. -
코드에서
g와h사이를 지나는지 검사하기 위해
if s_dist[target] == GH + min(s_dist[g] + h_dist[target], s_dist[h] + g_dist[target])조건문에 대한 검사를 수행하는데 -
INF = float('inf')로 지정한 경우 INF + 어떤 다른 수 == INF 이기 때문에target에 도달할 수 있을 뿐만 아니라g와h사이를 지나기도 한다고 판단한다. 따라서 올바른 결과를 얻지 못한다. -
이를 방지하기 위해
INF를float('inf')가 아닌 다른 어떤 큰 값으로 초기화하거나,
아래 코드처럼s에서target까지의 거리가INF라면 도달 불가하다고 생각하고 스킵하는 방법으로 걸러줘야한다.
import sys
input = sys.stdin.readline
import heapq
INF = float('inf')
def dijkstra(s):
dist = [INF] * (n+1)
dist[s] = 0
hq = [(0, s)]
heapq.heapify(hq)
while hq:
node_wt, node = heapq.heappop(hq)
for next_node, weight in graph[node]:
if weight + node_wt < dist[next_node]:
dist[next_node] = weight + node_wt
heapq.heappush(hq, (weight + node_wt, next_node))
return dist
for _ in range(int(input())):
# n: 노드 개수, m: 간선 개수, t: 목적지 후보 개수
n, m, t = map(int, input().split())
# s: 출발지, g-h 간선은 반드시 지나는 간선임
s, g, h = map(int, input().split())
GH = 0 # g-h 간선의 거리
# 그래프 생성 - 인접리스트
graph = [[] for _ in range(n + 1)]
for __ in range(m):
# a와 b 사이에 거리 d인 간선이 있음
a, b, d = map(int, input().split())
graph[a].append((b, d)) # (노드, 거리)
graph[b].append((a, d))
if (a == g and b == h) or (a == h and b == g):
GH = d
# 목적지 후보
candidates = []
for __ in range(t):
candidates.append(int(input()))
candidates.sort()
# s에서의 dijkstra 최단거리 결과
s_dist = dijkstra(s)
# g에서의 dijkstra 최단거리 결과
g_dist = dijkstra(g)
# h에서의 dijkstra 최단거리 결과
h_dist = dijkstra(h)
# s -> target = (s -> g) + (g-h: GH) + (h -> target)
# s -> target = (s -> h) + (h-g: GH) + (g -> target)
answer = []
for target in candidates:
# 주의!!! INF == INF + INF
if s_dist[target] == INF:
continue
if s_dist[target] == GH + min(s_dist[g] + h_dist[target], s_dist[h] + g_dist[target]):
answer.append(target)
print(' '.join(list(map(str, answer))))참고 사이트
