2주차 키워드
그래프(vertex, edge, node, arc), BFS, DFS, 위상정렬
키워드가 별로 없는 듯 하지만 그래프와 관련된 알고리즘이 꽤 많다. 모두 숙지하도록 하자.
1. 벨만포드 알고리즘
한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘
음수 간선이 있어도 최적의 해를 찾을 수 있다.
# 노드의 개수, 간선의 개수를 입력
v, e = map(int, input().split())
# 모든 간선에 대한 정보를 담는 리스트 만들기
edges = []
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (v + 1)
# 모든 간선의 정보 입력
for _ in range(e):
a, b, c = map(int, input().split())
# a번 노드에서 b번 노드로 가는 비용이 c라는 의미 (a -> b 의 비용이 c)
edges.append((a, b, c))
def bellman_ford(start):
# 시작 노드에 대해서 초기화
distance[start] = 0
# 전체 v - 1번의 라운드(round)를 반복
for i in range(v):
# 매 반복마다 '모든 간선'을 확인한다.
for j in range(e):
cur_node = edges[j][0]
next_node = edges[j][1]
edge_cost = edges[j][2]
# 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if distance[cur_node] != INF and distance[next_node] > distance[cur_node] + edge_cost:
distance[next_node] = distance[cur_node] + edge_cost
# v번째 라운드에서도 값이 갱신된다면 음수 순환이 존재
if i == v - 1:
return True
return False
# 벨만 포드 알고리즘 수행
negative_cycle = bellman_ford(1)
# 음수 순환이 존재하면 -1 출력
if negative_cycle:
print("-1")
else:
# 1번 노드를 제외한 다른 모든 노드로 가기 위한 최단 거리를 출력
for i in range(2, v + 1):
# 도달할 수 없는 경우, -1 출력
if distance[i] == INF:
print("-1")
# 도달할 수 있으면 거리 출력
else:
print(distance[i])시간 복잡도 : O(VE)
2. 다익스트라 알고리즘
INF = int(1e9)
n,m=map(int,input().split())
start = int(input())
graph=[[] for i in range(n+1)]
distance=[INF]*(n+1)
for _ 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)
# 현재 처리된적이 있는 노드라면 pass
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])시간 복잡도 : O(ElogV) - 우선순위 힙 사용
✓프림 vs 다익스트라
프림 - MST 구하는 알고리즘
다익스트라 - 시작 노드에서 목표 노드까지의 최소 경로를 구하는 알고리즘
차이점
1. 프림은 다익스트라와 달리 두 노드 사이가 최단거리가 아닐 수도 있다.
2. 프림은 무향 그래프에서만 작동하고, 다익스트라는 무향, 유향 그래프에서 모두 작동한다.
3. 프림이 다익스트라를, 다익스트라가 프림을 보장해주지 않는다.
-> 최소스패닝트리가 최단경로트리를, 최단경로트리가 최소스패닝트리를 보장하지 않는다.
3. 위상 정렬
모든 원소를 방문하기 전에 큐가 비게 된다면 사이클이 존재함을 알 수 있다.
import sys
from collections import deque
input = sys.stdin.readline
# 노드의 개수와 간선의 개수 입력
v, e = map(int, input().split())
# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (v + 1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트
graph = [[] for _ in range(v + 1)]
for _ in range(e):
a, b = map(int, input().split())
graph[a].append(b)
indegree[b] += 1
# 위상 정렬 함수
def topology_sort():
result = []
q = deque()
for i in range(1, v + 1):
if indegree[i] == 0:
q.append(i)
while q:
now = q.popleft()
result.append(now)
# 해당 원소와 연결된 노드들의 진입차수에서 1빼기
for g in graph[now]:
indegree[g] -= 1
if indegree[g] == 0:
q.append(g)
# 위상 정렬 수행한 결과 출력
for res in result:
print(res, end=' ')
topology_sort()시간 복잡도 : O(V+E)
4. 플로이드-워셜 알고리즘
모든 지점에서 다른 모든 지점까지의 최단 경로를 구하는 알고리즘
import sys
input = sys.stdin.readline
INF = int(1e9)
# 노드의 개수(n)과 간선의 개수(m) 입력
n = int(input())
m = int(input())
# 2차원 리스트 (그래프 표현) 만들고, 무한대로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]
# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n + 1):
for b in range(1, n + 1):
if a == b:
graph[a][b] = 0
# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(m):
# A -> B로 가는 비용을 C라고 설정
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('INFINITY', end=' ')
else:
print(graph[a][b], end=' ')
print()
시간 복잡도 : O(V^3)
WEEK REVIEW
일주일이 금방 지나간다. 익숙해지지 않을 것 같았지만 결국 적응하고 익숙해졌다.
그렇기에, 더욱 내 시간을 밀도있게 보내야 한다. 익숙함은 나를 나태하게 하기 때문이다. 화이팅!
first in, last out