백준 17835 [면접보는 승범이네] 파이썬

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

 

# 백준 17835 면접보는 승범이네
# 여러 개의 면접장을 시작점으로 하여, 모든 도시에서 가장 가까운 면접장까지의 최소 거리 계산
# 역방향 그래프 + 다익스트라 (다중 시작점)

import sys, heapq
input = sys.stdin.readline

# N: 도시 개수, M: 도로 개수, K: 면접장의 개수
N, M, K = map(int, input().split())

# dist[i] : i번 도시에서 가장 가까운 면접장까지의 최소 거리
dist = [float('inf') for _ in range(N + 1)]

# rev_costs[i] : 도시 i로 들어오는 간선 (역방향 그래프 저장)
rev_costs = [[] for _ in range(N + 1)]

# 도로 정보 입력 (A → B, 비용 cost)
# 역방향 그래프로 저장 (B ← A)
for _ in range(M):
    A, B, cost = map(int, input().split())
    rev_costs[B].append((A, cost))

# 다익스트라 (여러 시작점 가능)
def dijkstra(starts):
    q = []
    # 모든 면접장을 시작점으로 큐에 삽입
    for start in starts:
        dist[start] = 0
        heapq.heappush(q, (0, start))
    while q:
        d, curr_city = heapq.heappop(q)

        # 이미 더 짧은 경로가 있으면 무시
        if dist[curr_city] < d:
            continue

        # 현재 도시에서 갈 수 있는 역방향 간선 탐색
        for next_city, next_cost in rev_costs[curr_city]:
            # 더 짧은 거리 발견 시 갱신
            if dist[curr_city] + next_cost < dist[next_city]:
                dist[next_city] = dist[curr_city] + next_cost
                heapq.heappush(q, (dist[next_city], next_city))

# 면접장 도시 리스트 입력
targets = list(map(int, input().split()))

# 다익스트라 실행 (모든 면접장이 시작점)
dijkstra(targets)

# dist[1:] 중 최댓값을 갖는 도시 찾기
max_idx = dist.index(max(dist[1:]))

# 결과 출력: 가장 먼 도시 번호, 그 거리
print(max_idx)
print(dist[max_idx])

다익스트라 알고리즘을 사용하되, 역방향그래프를 이용하여 면접장을 시작점으로 하여 각 도시까지의 최단 거리를 구하면 된다.

역방향 그래프+다익스트라알고리즘을 이용하면 N번돌리지않고, 1번만 돌리면 된다.

시간복잡도는 Mlog(N)

 

https://dongkam.tistory.com/543

백준 1238 [파티] 파이썬

파티 문제를 풀 때 역방향 다익스트라에 대해서 공부하여서 이번 문제는 쉽게 해결하였다.