[Algorithm] 17835. 면접보는 승범이네

17835: 면접보는 승범이네(다익스트라)

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

• 문제 티어 : G2
• 풀이 여부 : Failed
• 소요 시간 : 45:32

정답 코드 1 : 면접장 → 도시로 가는 풀이 (정답)

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)

접근코드 2 : 도시 → 면접장으로 가는 풀이 (시간초과)

# 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)

접근 방식

시간초과가 나지 않으려면 면접장에서 각 도시로의 최단거리를 기준으로 각 비용을 계산한 뒤,

그 중에서도 가장 먼 도시와 그 비용을 산출하는 역발상으로 접근해야 한다.

이를 위해서는,

1. 입력으로 받는 u → v : c 의 시작노드 → 도착노드 : 비용 을 역으로 저장 (면접장 → 도시로 가기때문)
2. 다익스트라 코드 내부에서 면접장의 개수만큼 우선순위 큐에 push
3. 다익스트라에서 비용을 비교해가며 최소 비용으로 경로 생성
4. 면접장이 아닌 도시 중에 최댓값을 가지는 도시와 그 비용 계산

위와 같은 로직으로 정답을 찾아나갈 수 있다.

접근 시행착오(+ 코드)

처음 생각한 접근 방식으로는,

1. 1~N의 도시를 순회하며, K개의 면접장이 위치한 K_pos 중, 가장 가까운 면접장을 찾아준다.
2. 다익스트라 함수의 final(도착점)으로 설정해서 N번의 다익스트라 함수를 호출한다.

위 방식으로 문제를 풀이했다. (접근코드 2 참조)

하지만 해당 문제에서의 N의 범위는 100,000이며 도로의 수인 M의 범위는 500,000이다.

기본적인 다익스트라 알고리즘은 간선의 개수를 E라고 했을 때 O(ElogE)임을 고려해,

접근코드 2의 방식은 N번의 순회 후 간선의 개수가 M인 입력값으로 다익스트라 알고리즘을 호출하기에

O(N * MlogM)의 시간복잡도가 나옴을 확인할 수 있다.

즉, 시간 제한인 1초를 한참 넘겨서 시간초과가 날 수밖에 없다.

배운점 또는 느낀점

다익스트라 알고리즘의 역발상이 필요했던 문제다.

시간초과가 나서 접근코드 2는 졌지만 잘 싸운 코드로 … ^.^

문제를 보고 특정 알고리즘을 사용하면 되겠다는 생각이 들어도! 그 알고리즘을 적용하기 위한 입력값의 전처리에 얼만큼의 비용이 필요한지 고려하자.