문제
문제
방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.
입력
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.
출력
첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.
내 풀이
인접 노드를 저장한 뒤 BFS로 풀어보려 했다.
from collections import deque
V, E = map(int, input().split())
K = int(input())
edges = [list(map(int, input().split())) for _ in range(E)]
adj = [[] for _ in range(V+1)]
for u, v, w in edges:
adj[u].append([v, w])
min_weight = [float('inf')]*(V+1)
min_weight[1] = 0
visited = [False]*(V+1)
visited[1] = True
q = deque([[1,0]])
while q:
tmp, weight = q.popleft()
for v, w in adj[tmp]:
visited[v]=True
q.append([v, weight+w])
min_weight[v] = min(min_weight[v], weight+w)
for result in min_weight[1:]:
if result == float('inf'):
print("INF")
else:
print(result)
ㅜㅜ
찾아보니까 정점 간 최단거리를 구할 때 사용하는 다익스트라 알고리즘이 있었다.
다익스트라(Dijkstra) 알고리즘
다익스트라 알고리즘은 그래프에서 주어진 시작점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다.
주로 양의 가중치(weight)를 가진 그래프에서 사용된다.
원리
- 시작 정점을 설정한다.
- 최단 거리 테이블을 모두 무한대로 초기화한다.
- 방문하지 않은 정점 중에서 최단 거리가 가장 짧은 정점을 선택한다.
- 해당 정점을 거쳐 다른 정점으로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
- 위 과정을 모든 정점이 선택될 때까지 반복한다.
파이썬 예제 코드
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
queue = []
heapq.heappush(queue, [distances[start], start])
while queue:
current_distance, current_node = heapq.heappop(queue)
if distances[current_node] < current_distance:
continue
for adjacent, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[adjacent]:
distances[adjacent] = distance
heapq.heappush(queue, [distance, adjacent])
return distances
graph = {
'A': {'B': 8, 'C': 1, 'D': 2},
'B': {},
'C': {'B': 5, 'D': 2},
'D': {'E': 3, 'F': 5},
'E': {'F': 1},
'F': {'A': 5}
}
print(dijkstra(graph, 'A'))풀이
1️⃣ 입력값으로 그래프를 만든다.
V, E = map(int, input().split())
K = int(input())
# 딕셔너리 생성
graph = {i: {} for i in range(1, V+1)}
# 라인마다 받아서 딕셔너리에 넣어주기
for _ in range(E):
u, v, w = map(int, input().split())
# 중복된 값이 없다는 보장이 문제에 없으니 중복되면 최솟값을 저장하도록 함 (안하면 틀리더라구요 ㅜ)
if v in graph[u]:
graph[u][v] = min(graph[u][v], w)
else:
graph[u][v] = w
# graph = {
# 1: {2: 2, 3: 3},
# 2: {3: 4, 4: 5},
# 3: {4: 6},
# 4: {},
# 5: {1: 1}
# }2️⃣ 다익스트라 함수 생성
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
queue = []
heapq.heappush(queue, [distances[start], start]))
while queue:
cur_dist, cur_node = heapq.heappop(queue)
if distances[cur_node] < cur_dist:
continue
for adj, weight in graph[node].items():
dist = cur_dist + weight
if dist < distance[adj]:
distances[adj] = dist
heapq.heappush(queue, [dist, adj])
return distances3️⃣ 나머지 로직
# 생성한 다익스트라 함수로 입력받은 그래프와 시작점 K 전달
distances = dijkstra(graph, K)
# value가 float('inf')라면, INF 출력
for key, val in distances.items():
if val == float('inf'):
print("INF")
else:
print(val)전체 코드
import heapq
V, E = map(int, input().split())
K = int(input())
graph = {i: {} for i in range(1, V+1)}
for _ in range(E):
u, v, w = map(int, input().split())
if v in graph[u]:
graph[u][v] = min(graph[u][v], w)
else:
graph[u][v] = w
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
queue = []
heapq.heappush(queue, [distances[start], start])
while queue:
cur_dist, cur_node = heapq.heappop(queue)
if distances[cur_node] < cur_dist:
continue
for adj, weight in graph[cur_node].items():
dist = cur_dist + weight
if dist < distances[adj]:
distances[adj] = dist
heapq.heappush(queue, [dist, adj])
return distances
distances = dijkstra(graph, K)
for key, val in distances.items():
if val == float('inf'):
print("INF")
else:
print(val)가보자
어흥🦁