WEEK03 - 컴퓨팅사고로의 전환3
3주차에는 그래프 탐색, DFS, BFS, 위상정렬 에 대한 내용들을 공부하였다.
트리(Tree)
노드(Node)와 간선(Edge)으로 구성된 자료구조를 트리 라고 한다.
트리는 Class로 구현할 수 있으며, 간단하게 부모노드를 key, 자식노드를 value로 한 Dict 형태나 부모노드를 index, 자식노드를 value로 한 List 형태로도 구현 가능하다. 일반적으로 노드와 노드의 연결관계를 나타내기 위해 인접리스트 또는 인접행렬을 사용한다.
이진트리란 부모노드에 2개의 자식노드가 붙어있는 형태를 말하며,
이진검색트리란 이진트리 중에서도 특정한 규칙이 있는 트리를 의미하는데, 부모노드를 기준으로 왼쪽트리는 모두 부모노드보다 작고 오른쪽트리는 부모노드보다 큰 규칙을 가진 트리를 말한다.
최소신장트리와 크루스칼 알고리즘
트리에서 노드들이 서로 연결되어 닫힌 구조가 되면 Cycle이 생겼다고 할 수 있는데,
이 싸이클이 없으면서 모든 노드들이 간선으로 연결된 경우 신장트리라고 한다.
그 중에서도, 간선들의 가중치 합이 가장 작은 경우를 최소신장트리라고 한다.
최소신장트리의 가중치 합을 구하는 알고리즘 중의 하나가 크루스칼 알고리즘이다.
크루스칼 알고리즘은 간선의 가중치를 오름차순으로 정렬한 후 낮은 가중치를 갖는 두 정점(Vertex)부터 확인하며, 두 정점이 Cycle을 형성하지 않는 경우 두 정점을 잇는 과정으로 이루어진다.
두 정점이 Cycle을 형성하는지 확인하고 잇는 과정의 경우 Union-Find 알고리즘을 사용한다. Union-Find 알고리즘은 겹치는 노드가 없는 트리, 즉 서로소인 트리를 찾고 연결하는 알고리즘이다. Find 함수는 한 정점의 부모노드를 반환하며, Union 함수는 Find 함수를 호출하여 두 노드의 부모노드를 알아낸 후 부모노드가 서로 다르다면 두 노드를 합친다. 이 과정에서 잇게되는 가중치에 대해 누적합을 구하면 최소신장트리의 가중치 합을 구할 수 있다.
# 입력
V, E = map(int,input().split())
edges = []
for _ in range(E) :
A,B,C = map(int,input().split())
edges.append((C,(A,B)))
# 가중치 기준 오름차순 정렬
edges.sort()
# 최소신장트리의 가중치 합 담는 변수
rst = 0
# 대표 vertex (부모) 저장
parents = [i for i in range(V+1)]
# 대표 vertex 반환 / 평탄화 함수
def find(n) :
# 부모를 찾고 자기 자신이면 바로 반환, 자기 자신이 아니면 재귀적 호출 후 대표점 반환
if parents[n] != n :
parents[n] = find(parents[n])
return parents[n]
return parents[n]
# 합치는 함수
def union(a,b) :
pa = find(a)
pb = find(b)
# print("a : %d, b : %d, pa : %d, pb : %d" %(a,b,pa,pb))
# a와 b의 대표점이 다르면 연결안된 그래프이므로 연결, 같으면 합치지 않음.
if pa != pb :
# 실제 가리키는게 중요한게 아니라 연결이 되는게 중요하기 때문에 현재 것들끼리 연결일 필요가 없음. 부모끼리 한 방향으로 연결만 되면 됨.
parents[pa] = pb
# print("parents[%d] = %d" %(a,b))
# print(parents)
return True
return False
for edge, vs in edges :
a, b = vs
if union(a,b) :
rst += edge
print(rst)DFS와 BFS
그래프를 탐색하는 대표적인 방법에는 DFS, BFS 두가지가 있다.
DFS(Depth First Search: 깊이우선탐색) 란 한 노드에 연결된 자식노드들 중 한가지의 노드를 탐색하고, 연결된 노드가 더이상 없을때까지 이 과정을 반복한 뒤에 또 다른 노드를 같은 방법으로 탐색하는 방법이다. 한 노드에서 자식노드로의 탐색하는 과정이 반복되기에 재귀함수로 구현할 수 있으며, 스택과 반복문으로도 구현 가능하다.
# 스택을 활용한 DFS 함수 구현
def DFS(start) :
stk = [] # 탐색해야할 노드를 임시 저장하는 스택
visit = [False] * (N+1) # 한번 방문한 곳은 다시 방문하지 않도록 방문처리하는 배열
stk.append(start)
while stk : # stk에 노드가 들어있는 동안 반복
v = stk.pop()
visit[v] = True # 스택에서 나올때 방문처리
for i in graph[v] : # 정점에 연결된 노드들에 대하여 반복
if not visit[i] : # 정점을 방문하지 않았다면
stk.append(i) # 스택에 저장
BFS(Breadth First Search: 너비우선탐색) 란 한 노드에 연결된 모든 노드에 대해서 우선탐색하는 방법이다. 큐를 사용하여 구현 가능하다.
# 큐를 활용한 BFS 함수 구현
from collections import deque
def BFS(start) :
que = deque()
visit = [False] * (N+1)
que.append(start)
while que :
v = que.popleft()
for i in graph[v] :
if not visit[i] :
que.append(i)
visit[i] = True # 큐에 넣을때 방문처리다익스트라(Dijkstra) 알고리즘
다익스트라 알고리즘이란 한 정점으로부터 나머지 정점들까지의 최단거리를 구하는 알고리즘이다.
시작점으로부터 연결된 간선 중 최소거리의 간선을 갖는 정점을 선택하고 이 정점과 연결된 정점을 이으면서 최소값을 갱신해나가는 과정으로 이루어진다. (자세한 설명은 이코테 강의 참고)
# bfs를 활용한 다익스트라 구현
distance = [INF] * (V+1) # 모든 노드로의 거리를 무한대로 초기화
def daijkstra(lv) :
que = []
distance[lv] = 0 # 시작점부터 시작점까지의 거리는 0 으로 입력
heappush(que,(0,lv))
while que :
d, s = heappop(que) # 최소값 빼내기
if d > distance[s] : continue # 이미 확인하여 최소값이 갱신된 경우는 pass
for w, e in graph[s] :
cost = d + w
if cost < distance[e] : # 최소비용이 갱신가능하다면
distance[e] = cost # 갱신하고
heappush(que,(cost,e)) # queue에 넣어줌위상정렬(Topological Sort)
위상정렬이란 방향이 있고 Cycle이 없는 그래프에서 정점들을 순서대로 나열하는 것을 의미한다. 여기서 정렬은 일반적인 정렬과 의미가 다르다.
한 노드에 대해서 들어오는 방향의 개수를 진입차수(Indegree)라고 하며 나가는 방향의 개수를 진출차수(Outdegree)라고 한다. 진입차수가 0인 노드를 queue에 넣는 과정을 반복함으로써 위상정렬을 구현할 수 있다.
# 위상정렬의 기본적인 틀
graph = [[] for _ in range(N+1)]
indegree = [0] * (N+1) # 진입차수 0으로 초기화
for _ in range(M) :
A, B = map(int,input().split())
graph[A].append(B)
indegree[B] += 1 # 들어오는 방향에 노드가 있을 때마다 진입차수 1씩 증가
que = deque()
for i in range(1,N+1) :
if indegree[i] == 0 : # 진입차수가 0이면 큐에 넣기
que.append(i)
while que :
v = que.popleft()
for i in graph[v] :
indegree[i] -= 1 # 방문할때마다 진입차수 1씩 감소
if indegree[i] == 0 : # 진입차수가 0이되면
que.append(i) # 큐에 넣기