https://www.acmicpc.net/problem/17835
Failed
import sys, heapq
input = sys.stdin.readline
N, M, K = map(int, input().rstrip().split())
arr = [[] for _ in range(N+1)] # 1 ~ N개의 도시
for _ in range(M): # O(M)
u, v, c = map(int, input().rstrip().split())
arr[v].append((u, c)) # v -> u : c (시작점을 면접장으로 설정할 것이므로 u -> v 경로를 v -> u로 바꿔서 보기)
K_pos = list(map(int, input().rstrip().split())) # 면접장의 위치
def dijkstra(arr, starts):
costs = [float('inf') for _ in range(N+1)]
pq = []
# 면접장 위치에서 시작하도록 다익스트라 초기화
for start in starts:
heapq.heappush(pq, (0, start)) # 누적비용, 노드
costs[start] = 0
while pq:
cur_cost, cur_node = heapq.heappop(pq)
if costs[cur_node] < cur_cost:
continue
for next_node, cost in arr[cur_node]:
next_cost = cur_cost + cost
if next_cost < costs[next_node]:
costs[next_node] = next_cost
heapq.heappush(pq, (next_cost, next_node))
return costs
dist = dijkstra(arr, K_pos)
max_dist, max_city = 0, 0
for i in range(1, N+1): # 가장 먼 노드 탐색 O(N)
if i not in K_pos and dist[i] > max_dist:
max_dist = dist[i]
max_city = i
print(max_city)
print(max_dist)
# O(N * (MlogM))
import sys, heapq
input = sys.stdin.readline
# N: 도시의 수, M: 도로의 수, K: 면접장의 수
N, M, K = map(int, input().split())
arr = [[] for _ in range(N + 1)]
# 도로 정보 입력 받기 (단방향)
for _ in range(M):
u, v, c = map(int, input().split())
arr[u].append((v, c)) # u에서 v로 가는 비용이 c
# 면접장 위치 입력 받기
K_pos = list(map(int, input().split()))
# 다익스트라 알고리즘
def dijkstra(start):
costs = [float('inf')] * (N + 1)
costs[start] = 0
pq = [(0, start)]
while pq:
cur_cost, cur_node = heapq.heappop(pq)
if costs[cur_node] < cur_cost:
continue
for next_node, cost in arr[cur_node]:
distance = cur_cost + cost
if distance < costs[next_node]:
costs[next_node] = distance
heapq.heappush(pq, (distance, next_node))
return costs
# 각 도시에서 면접장까지의 최단 거리 중 최댓값 찾기
max_dist, max_city = 0, 0
for start_city in range(1, N + 1): # O(N)
if start_city in K_pos:
continue
dist = dijkstra(start_city) # O(MlogM)
# 면접장 중 가장 가까운 거리 찾기
min_k = min([dist[loc] for loc in K_pos])
if min_k > max_dist:
max_dist = min_k
max_city = start_city
print(max_city)
print(max_dist)
시간초과가 나지 않으려면 면접장에서 각 도시로의 최단거리를 기준으로 각 비용을 계산한 뒤,
그 중에서도 가장 먼 도시와 그 비용을 산출하는 역발상으로 접근해야 한다.
이를 위해서는,
u → v : c
의 시작노드 → 도착노드 : 비용
을 역으로 저장 (면접장 → 도시로 가기때문)위와 같은 로직으로 정답을 찾아나갈 수 있다.
처음 생각한 접근 방식으로는,
K_pos
중, 가장 가까운 면접장을 찾아준다.위 방식으로 문제를 풀이했다. (접근코드 2 참조)
하지만 해당 문제에서의 N의 범위는 100,000이며 도로의 수인 M의 범위는 500,000이다.
기본적인 다익스트라 알고리즘은 간선의 개수를 E라고 했을 때 O(ElogE)임을 고려해,
접근코드 2의 방식은 N번의 순회 후 간선의 개수가 M인 입력값으로 다익스트라 알고리즘을 호출하기에
O(N * MlogM)의 시간복잡도가 나옴을 확인할 수 있다.
즉, 시간 제한인 1초를 한참 넘겨서 시간초과가 날 수밖에 없다.
다익스트라 알고리즘의 역발상이 필요했던 문제다.
시간초과가 나서 접근코드 2는 졌지만 잘 싸운 코드로 … ^.^
문제를 보고 특정 알고리즘을 사용하면 되겠다는 생각이 들어도! 그 알고리즘을 적용하기 위한 입력값의 전처리에 얼만큼의 비용이 필요한지 고려하자.