✅ 문제 풀이 - BOJ (다익스트라)
🎈 1238 파티
N개의 숫자로 구분된 각 마을에 한 명의 학생이 살고 있고 N명의 학생이 x번째 마을에 모여 파티를 한다고 할때, 각 학생들은 마을 사이에 있는 m개의 단 방향 도로의 i번째 길을 지나오며 t시간을 소비하다고 한다. 각 학생이 파티에 참석하기 위해 걸어서 한 마을에 모인 뒤 다시 그들의 마을로 돌아갈 때 가장 많이 시간을 소비하는 학생을 출력하는 문제
입출력은 다음과 같다
- 입력: 첫 줄에 학생 수(마을 수)n, 도로 수 m, 모이는 마을 장소 x 이후 m줄만큼 i번째 도로 시작, 끝, 소요시간이 주어진다.
- 출력 : n명이 학생들 중 가장 오래 시간을 소요하는 학생의 걸리는 시간 출력
import sys
input = sys.stdin.readline
import heapq
n, m, x = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
start, end, time = map(int, input().split())
graph[start].append((end, time))
def dijkstra(start):
total_time = [int(1e9)] * (n + 1)
heap = []
heapq.heappush(heap, (start, 0))
total_time[start] = 0
while heap:
node, time = heapq.heappop(heap)
if total_time[node] < time:
continue
for next_node, next_time in graph[node]:
if time + next_time < total_time[next_node]:
total_time[next_node] = time + next_time
heapq.heappush(heap, (next_node, time + next_time))
return total_time
dist = [[]]
for i in range(1, n+1):
dist.append(dijkstra(i))
answer = []
for i in range(1, n+1):
answer.append(dist[i][x] + dist[x][i])
print(max(answer))< 풀이 과정 >
우선순위 큐 (heapq)를 활용한 다익스트라의 전체적인 틀은 대부분 변하질 않는다.
다익스트라 함수를 이용하여 각 노드 별 모든 정점까지 소요되는 최소 시간을 total_time으로 리턴해준 후, for문으로 1~n까지의 노드를 대상으로 다익스트라 함수를 돌려 dist라는 2차원리스트로 저장한다.
예제의 결과대로면 dist는 다음과 같다.
- dist : [[], [1000000000, 0, 4, 2, 6], [1000000000, 1, 0, 3, 7], [1000000000, 2, 6, 0, 4], [1000000000, 4, 3, 6, 0]]
이 의미는 0, 1, 2, 3, 4순서대로 각 마을에서 해당 노드로 이동하는 데 소요되는 최소 시간을 저장한 것을 의미한다.
최종적으로 각 i마을에 위치한 사람들이 x마을에서 파티를 한 후 다시 i마을로 돌아가야 하므로, 위 dist를 dist[i][x] + dist[x][i]를 이용하여 answer에 저장한 후 가장 시간이 오래걸린 학생이 소요한 시간을 max함수로 뽑아주면 된다.
🎈 1504 특정한 최단 경로
방향성이 없고 정점이 n개인 그래프에서 1번 노드에서 n번 노드로 이동하고자 한다.
두 가지 조건을 만족하며 이동하는 특정 최단 경로를 구하려하는데, 조건은 다음과 같다.
- 임의로 주어진 두 노드는 반드시 통과
- 한번 이동한 노드, 간선은 다시 방문 가능하지만 최단 경로이어야 한다.
입출력은 다음과 같다- 입력: 첫 줄에 노드 수 n, 간선 수 e, e줄만큼 시작점 a, 도착점 b, 거리가 c로 주어지고 마지막줄에는 반드시 거쳐야 하는 노드 2개가 주어진다.
- 출력 : 두 정점을 지나는 최단 경로 길이를 출력하고, 경로가 없다면 -1을 출력
import sys
input = sys.stdin.readline
import heapq
n, e = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(e):
a, b, c = map(int, input().split())
graph[a].append((b, c))
graph[b].append((a, c))
def dijkstra(start, end):
distance = [int(1e9)] * (n+1)
distance[start] = 0
heap = []
heapq.heappush(heap, (start, 0))
while heap:
node, dist = heapq.heappop(heap)
if distance[node] < dist:
continue
for next_node, next_dist in graph[node]:
if dist + next_dist < distance[next_node]:
distance[next_node] = dist + next_dist
heapq.heappush(heap, (next_node, dist + next_dist))
return distance[end]
v1, v2 = map(int, input().split())
path1 = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, n)
path2 = dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, n)
if path1 >= int(1e9) and path2 >= int(1e9):
print(-1)
else:
print(min(path1, path2))< 풀이 과정 >
입력값 생성 후, 양방향 간선으로 그래프를 생성한다.
dijkstra함수는 start, end를 입력받아 기본적인 frame은 일치시키고 최종적인 리턴값만 distance[end]로 넣어 start -> end로 이동하는 최소 이동 거리를 출력하도록 만든다.
그 이후 1번노드에서 n번노드로 이동하는데, 주어진 정점 v1, v2를 반드시 지나야하므로 path1, path2로 지정한 다음 최단 경로가 없다면 -1을, 있다면 path1, path2를 비교하여 최솟값을 출력한다.
