👀 Week02 요약
어느새 알고리즘 2주차! 이번 주에는 아래 내용들을 살펴보았다.
이번 개발일지에서는 앞으로 두고두고 사용할 핵심 코드에 대해 정리해보고자 한다.
코드들의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트다 with Python GitHub이다.
1) 스택
2) 큐
3) 우선순위 큐
4) 그래프
5) BFS
6) DFS
7) 위상정렬
1️⃣ 최소 스패닝 트리
최소 스패닝 트리 (Minimum Spanning Tree)는 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.
최소 스패닝 트리와 관련해서 대표적인 알고리즘은 크루스칼 알고리즘(Kruskal Algorithm)이고, 아래와 같은 코드로 구현할 수 있다.
# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
# 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
# 노드의 개수와 간선(Union 연산)의 개수 입력 받기
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화하기
# 모든 간선을 담을 리스트와, 최종 비용을 담을 변수
edges = []
result = 0
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
parent[i] = i
# 모든 간선에 대한 정보를 입력 받기
for _ in range(e):
a, b, cost = map(int, input().split())
# 비용순으로 정렬하기 위해서 튜플의 첫 번째 원소를 비용으로 설정
edges.append((cost, a, b))
# 간선을 비용순으로 정렬
edges.sort()
# 간선을 하나씩 확인하며
for edge in edges:
cost, a, b = edge
# 사이클이 발생하지 않는 경우에만 집합에 포함
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
result += cost
print(result)2️⃣ 다익스트라 최단 경로 알고리즘
다익스트라 알고리즘은 최단 경로를 찾는데 사용되는 그래프 알고리즘 중 하나로, 하나의 시작 노드로부터 모든 다른 노드까지의 최단 경로를 구하는 데 활용된다.
단, 간선의 가중치가 음의 가중치를 갖는다면 다익스트라 알고리즘을 사용할 수 없다.
🚀 다익스트라 알고리즘 구현 방법
-
시작노드로부터의 최단 거리를 저장하는 배열의 값을 모두 무한대로 초기화한다.
-
시작 노드에서부터 출발해서 현재 노드와 연결된 인접 노드들을 방문하면서 최단 거리를 업데이트 한다. 이때 방문하지 않은 노드들 중에서 거리가 가장 짧은 노드부터 방문하기 위해 우선순위 큐를 사용한다.
-
모든 노드를 방문할 때까지, 즉 큐가 빌 때까지 2번 단계를 반복한다. 이때, 이미 최단 거리가 확정된 노드는 다시 방문하지 않는다. (
if distance[now] < dist: continue)
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# 노드의 개수, 간선의 개수를 입력받기
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())
# a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].append((b, c))
def dijkstra(start):
q = []
# 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
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):
# 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if distance[i] == INF:
print("INFINITY")
# 도달할 수 있는 경우 거리를 출력
else:
print(distance[i])