다익스트라 알고리즘
시간 복잡도 : O(V^2)
import sys
input = sys.stdin.readline
INF = int(1e9)
n,m = map(int,input().split())
start = int(input())
graph = [[] for i in range(n+1)]
visited = [False] * (n+1)
distance = [INF] * (n+1)
for _ in range(m):
a,b,c = map(int, input().split())
graph[a].append((b,c))
def get_smallest_node():
min_value = INF
index = 0
for i in range(1,n+1):
if distance[i] < min_value and not visited[i]:
min_value = distance[i]
index = i
return index
def dijkstra(start):
distance[start] = 0
visited[start] = True
for j in graph[start]:
distance[j[0]] = j[1]
for i in range(n-1):
now = get_smallest_node()
visited[now] = True
for j in graph[now]:
cost = distance[now] + j[1]
if cost < distance[j[0]]:
distance[j[0]] = cost
dijkstra(start)
for i in range(1,n+1):
if distance[i] == INF:
print("INFINITY")
else:
print(distance[i])결과 값)
heapq를 이용한 다익스트라
import heapq
import sys
input = sys.stdin.readline
INF = 1e9
n,m = map(int,input().split())
start = int(input())
graph= [[] for i in range(n+1)]
distance = [INF] * (n+1)
for i in range(m):
a,b,c = map(int, input().split())
graph[a].append((b,c))
def dijkstra(start):
q =[]
heapq.heappush(q,(0,start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
if distance[now] < dist:
continue
for i in graph[now]:
cost = dist + i[1]
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q,(cost,i[0]))
dijkstra(start)
for i in range(1,n+1):
if distance[i] == INF:
print("INFINITY")
else:
print(distance[i])코드를 이해하고 왜 이렇게 작성했는지를 공부하는 것이 중요한것 같다. 그러지 않으면 외우기가 힘들어... 내 뇌는 멍청하거든
다익스트라 알고리즘은 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우'에 사용할 수 있는 최단경로 알고리즘이다. 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘이다.
다익스트라 알고리즘은 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다. 그리고 해당 노드를 거쳐 가는 경로를 확인하며, 최단 거리 테이블을 갱신하는 방식으로 동작한다. 플로이드 워셜 알고리즘 또한 단계마다 '거쳐 가는 노드'를 기준으로 알고리즘을 수행한다. 하지만 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다는 점이 다르다. 노드의 개수가 N개일 때 알고리즘상으로 N번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 현재 노드를 거쳐가는 모든 경로를 고려한다. 따라서 플로이드 워셜의 총시간 복잡도는 O(N^3)이다.
플로이드 워셜 알고리즘
INF = int(1e9)
n,m = map(int,input().split())
graph = [[INF] * (n+1) for i in range(n+1)]
for a in range(1,n+1):
for b in range(1,n+1):
if a == b:
graph[a][b] = 1
for _ in range(m):
a,b,c = map(int,input().split())
graph[a][b] = c
for k in range(1,n+1):
for a in range(1,n+1):
for b in range(1,n+1):
graph[a][b] = min(graph[a][b],graph[a][k]+graph[k][b])
for a in range(1,n+1):
for b in range(1,n+1):
if graph[a][b] == INF:
print('INF', end = '')
else:
print(graph[a][b], end ='')
print()실전문제 - 미래도시 p.259
풀이)
INF = int(1e9)
n,m = map(int,input().split())
graph = [[INF] * (n+1) for i in range(n+1)]
for a in range(1,n+1):
for b in range(1,n+1):
if a == b:
graph[a][b] = 1
for i in range(m):
a,b = map(int,input().split())
graph[a][b] = 1
graph[b][a] = 1
x,k = map(int,input().split())
for k in range(1,n+1):
for a in range(1,n+1):
for b in range(1,n+1):
graph[a][b] = min(graph[a][b],graph[a][k]+graph[k][b])
distance = graph[1][k] + graph[k][x]
if distance >= INF:
print(-1)
else:
print(distance)comment) 문제를 보고 최단 경로 문제구나 판단을 하고 플로이드 워셜을 쓸건지 다익스트라를 쓸건지 구분 하고 풀어야 할 것 같다. 일단 두 알고리즘을 외우는 건 필수인 것 같고, 나머지 한개의 알고리즘이 있다는 데 그것도 공부해야 할 것 같다.
여기서 n,m의 범위가 1 부터 100까지여서 시간 복잡도가 n^3인 플로이드를 사용할 수 있는 것 같다
실전문제 - 전보 p.263
풀이)
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
n,m,start = map(int,input().split())
graph =[[] for i in range(n+1)]
for _ in range(m):
# a ->b cost = c
a,b,c = map(int,input().split())
graph[a].append((b,c))
distance = [INF] * (n+1)
def dijkstra(start):
q =[]
heapq.heappush(q,(0,start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
if distance[now] < dist:
continue
for i in graph[now]:
cost = dist + i[1]
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q,(cost,i[0]))
dijkstra(start)
count = -1
time = []
for i in range(n+1):
if distance[i] != INF:
count += 1
time.append(distance[i])
print(time)
print(count,max(time),sep = ' ')comment)
일단 최단 경로문제의 유형은 대충 파악할 것 같다. 특정 노드에서 출발은 다익스트라를 응용해서 풀면 되고 현재 노드를 거쳐가는 문제는 플로이드 워셜을 응용해서 사용하면 되는 것 같다. 물론 문제가 이렇게 쉽게 나올려나 싶지만 일단은 처음으로 책 안보고 나혼자 해결한 문제라 기분은 좋다.
