1238번_파티
https://www.acmicpc.net/problem/1238
문제 요약
1. N개의 마을에 각각 한 명의 학생이 살고 있다.
2. 그 중 하나의 마을(X번)에서 파티를 하는데 모든 학생들이 X번 마을로 모였다가 돌아가야한다.
3. 이 때 모든 학생들은 최단 시간으로 움직여야한다.
4. 학생들 중 가장 시간이 오래 걸리는 학생을 찾는다.
=>다익스트라(dijkstra) 알고리즘이용해야한다.
다익스트라(dijkstra) 알고리즘
개념
- 다익스트라 알고리즘은 그래프에서 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘.
- 매 번 시작 정점에서 모든 정점까지의 최단 경로를 찾게 된다
동작 과정
- 출발 지점을 정한다.
- '최단 거리(가중치) 테이블'을 초기화한다.
- 현재 노드와 연결된 노드 중 방문하지 않았고, 거리가 가장 짧은 노드를 선택한다.
- 선택한 노드와 연결된 노드로 이동할 때의 가중치를 기존의 가중치와 비교하여 '최단 거리(가중치) 테이블'을 업데이트한다.
- 3, 4번 과정 반복
위 문제에서는 모든 학생이 파티에 갔다가 돌아와야하므로
모든 노드 -> X,X -> 모든 노드방향으로 두 번의 다익스트라 알고리즘 과정이 필요했다.
# 시간 초과!
def dijkstra(s):
visited = [0] * (N+1)
D = [float('inf')] * (N+1) # 최단 거리 테이블 설정
D[s] = 0 # 시작 노드를 최솟값(0)으로 설정
for _ in range(N):
idx = -1
minv = float('inf')
for k in range(1, N+1): # 동작 과정 3번
if not visited[k] and D[k] < minv:
minv = D[k]
idx = k
visited[idx] = 1
for v, val in city[idx]: # 동작 과정 4번
if not visited[v] and val + D[idx] < D[v]:
D[v] = val + D[idx]
return D
N, M, X = map(int, input().split())
city = [[] for _ in range(N+1)]
for _ in range(M):
a, b, t = map(int, input().split())
city[a].append([b, t]) # 인접 노드 리스트
# X -> 모든 노드 최단 시간 구하기
ans = dijkstra(X)
ans[0] = 0
for i in range(1, N+1):
if i != X: # X가 시작점인 경우는 이미 구했으니 제외
res = dijkstra(i) # 모든 노드 -> X 최단 시간 구하기
ans[i] += res[X]
print(max(ans))그러나 위와 같은 방법으로는 시간 초과가 났고, 힙(heap)을 이용한 다익스트라 알고리즘으로 다시 풀었다.
힙(heap)을 이용한 다익스트라 알고리즘
: 힙 이용 없이 구현하면, 매번 최단 거리가 가장 짧은 노드를 순차 탐색해야 하고, 현재 노드와 연결된 노드를 매번 확인해야 한다. -> 시간 초과 발생
힙을 이용하게 되면, 최단 거리 정보를 힙에 담아 처리하므로 출발 노드부터 가장 거리가 짧은 노드를 빠르게 찾을 수 있다.
힙(heap)
- 최댓값과 최솟값을 빠르게 찾기 위해 고안된 자료 구조 (완전 이진트리 구조)
- 파이썬의 경우
heapq라이브러리로최소 힙이 지원된다.최소 힙은 부모 노드 값 < 자식 노드 값,최대 힙은 부모 노드 값 > 자식 노드 값최소 힙은 값이 낮은 데이터가 먼저 삭제되고,최대 힙은 값이 큰 데이터가 먼저 삭제된다.- 파이썬 heapq를 이용하면 시간 복잡도
O(NlogN)에 오름차순 정렬이 완료됨.
import heapq
def dijkstra(s):
D = [float('inf')] * (N+1)
D[s] = 0
q = [] # 최단 거리 테이블을 heap으로 구현
heapq.heappush(q, (0, s)) # heap에 (가중치, 노드) 형식으로 삽입
while q:
dist, now = heapq.heappop(q) # 최소힙이므로 가중치가 가장 작은 값이 pop
if D[now] >= dist: # 이미 최솟값 구했는지 확인
for v, val in city[now]: # 연결된 노드들 확인
if dist + val < D[v]: # 가중치가 더 작은 값이면 갱신
D[v] = dist + val
heapq.heappush(q, (dist + val, v))
return D
N, M, X = map(int, input().split())
city = [[] for _ in range(N+1)]
for _ in range(M):
a, b, t = map(int, input().split())
city[a].append([b, t])
ans = dijkstra(X)
ans[0] = 0
for i in range(1, N+1):
if i != X:
res = dijkstra(i)
ans[i] += res[X]
print(max(ans))참고 자료
