지금까지의 그래프 알고리즘 및 이론 정리
그래프(Graph) 요약
- 구성요소
- 노드(Node) / 정점(Vertex)
- 간선(Edge)
- 프로그래밍 언어에서 그래프 표현 방법
- 인접 행렬
- 인접 리스트
DFS/BFS → DFS/BFS (Graph Traversal)
- DSF
- 스택(재귀)을 이용한 그래프 탐색
- BFS
- 큐를 이용한 그래프 탐색
최단 경로 → 최단 경로 (Shortest Path)
- 단일 쌍의 최단거리
- 다익스트라
- 그리드
- 인접 리스트
- 다익스트라
- 모든 쌍의 최단거리
- 플루이드 워셜
- 다이나믹 프로그래밍
- 인접 행렬
- 플루이드 워셜
트리
- 그래프의 한 종류
- 부모에서 자식으로 내려오는 계층적 모델
- 전통적인 수학에서는 무방향 그래프로 간주되지만, 컴퓨터공학 분야에서는 보통 방향 그래프라고 간주
- $간선의 개수 = 노드의 개수-1$ 인 특징을 가짐
그래프와 트리 비교
전체 윤곽 보고가기
서로소 집합 자료구조에 대해 알아봄
→ 무방향 그래프에서의 사이클(순환) 여부 판별에 활용할 수 있음
→ 최소 신장 트리를 구하기 위한 크루스칼 알고리즘에 활용
위상 정렬에 대해 알아봄
서로소 집합 (Disjoint Sets) 자료구조
서로소 집합
- 공통 원소가 없는 두 집합을 의미
- 예) 집합 {1, 2}와 {3, 4}는 서로소 관계
서로소 집합 자료구조 (union-find)
서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
연산 종류
- union (합집합) : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
- find (찾기) : 특정한 원소가 속한 집합이 어떤 집합인지(루트 노드가 무엇인지) 알려주는 연산
구현 방법
1. union 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인
i . A와 B의 루트 노드 A’, B’를 각각 찾음
ii. A’를 B’의 부모 노드로 설정 (B’가 A’를 가리키도록 함)
2. 모든 union 연산을 처리할 때까지 1번 과정을 반복
- 트리 자료구조 이용
- A’와 B’ 중에 더 번호가 작은 원소가 부모 노드가 되도록 구현하는 경우가 많음
- ’가리킨다‘는 의미는 부모 노드로 설정한다는 것
동작 예시
- 전체 집합 {1, 2, 3, 4, 5, 6}
- 연산
- union 1, 4 → 1과 4는 같은 집합 의미
- union 2, 3 → 2과 3는 같은 집합 의미
- union 2, 4 → 2과 4는 같은 집합 의미
- union 5, 6 → 5과 6는 같은 집합 의미
- 동작 방식
- union연산을 하나씩 확인(루프) → 서로 다른 두 원소에 대해 합집합을 수행 (각각 루트 노드를 찾아서 더 큰 루트 노드가 더 작은 루트 노드를 가리키도록 설정)
가장 먼저 노드의 개수(V) 크기의 부모 테이블 초기화
- 자기 자신을 부모로 갖도록 초기화
- 부모 테이블은 해당 노드의 부모에 대한 정보만을 가짐
- 루트 노드 확인을 위해서는 재귀적으로 부모를 거슬러 올라가 최종적인 루트 노드를 찾아야함
union 1, 4 : 1과 4를 합침
1과 4의 루트 노드를 각각 찾아 (현재는 각각 1과 4) 더 큰 번호에 해당하는 루트 노드 4의 부모를 1로 설정
union 2, 3 : 2와 3을 합침
2와 3의 루트 노드를 각각 찾아 (현재 각각 2와 3) 더 큰 번호에 해당하는 루트 노드 3의 부모를 2로 설정
union 2, 4 : 2와 4를 합침
2와 4의 루트 노드를 각각 찾아 (현재 각각 2와 1) 더 큰 번호에 해당하는 루트 노드 2의 부모를 1로 설정
union 5, 6 : 5와 6을 합침
5와 6의 루트 노드를 각각 찾아 (현재 각각 5와 6) 더 큰 번호에 해당하는 루트 노드 6의 부모를 5로 설정
union 연산 모두 완료
- 위 과정에서 유의할 점
- union연산을 효과적으로 수행하기 위해 ‘부모 테이블’을 항상 가지고 있어야 함
- 루트 노드를 즉시 계산할 수 없고, 부모 테이블을 거슬러 올라가야 함
구현
기본적인 서로소 집합 알고리즘
# 특정 원소가 속한 집합 찾기
def find_parent(parent, x):
# 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if parent[x] != x:
return find_parent(parent, parent[x])
return 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) # 부모 테이블 초기화
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
parent[i] = i
# union 연산을 각각 수행
for i in range(e):
a, b = map(int, input().split())
union_parent(parent, a, b)
# 각 원소가 속한 집합 출력
print('각 원소가 속한 집합: ', end='')
for i in range(1, v + 1):
print(find_parent(parent, i), end=' ')
print()
#부모 테이블 내용 출력
print('부모 테이블: ', end='')
for i in range(1, v + 1):
print(parent[i], end=' ')
print()
경로 압축 기법을 적용한 서로소 집합 알고리즘
# 특정 원소가 속한 집합 찾기
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) # 부모 테이블 초기화
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
parent[i] = i
# union 연산을 각각 수행
for i in range(e):
a, b = map(int, input().split())
union_parent(parent, a, b)
# 각 원소가 속한 집합 출력
print('각 원소가 속한 집합: ', end='')
for i in range(1, v + 1):
print(find_parent(parent, i), end=' ')
print()
#부모 테이블 내용 출력
print('부모 테이블: ', end='')
for i in range(1, v + 1):
print(parent[i], end=' ')
print()
기본적인 서로소 집합 알고리즘의 문제점
find함수가 비효율적으로 동작함find시 최악의 경우 $O(V)$가 될 수 있음 → 전체 시간 복잡도가 $O(VM)$ (M: union 연산 개수) 가 될 수 있음
경로 압축 (Path Compression) 기법 적용
find함수를 재귀적으로 호출한 뒤에 부모 테이블의 값을 갱신하는 기법- 각 노드에 대해
find함수를 호출한 이후에, 해당 노드의 루트 노드가 바로 부모 노드가 되어 시간 복잡도가 개선됨 - 시간 복잡도 : $O(V+M(1+log_{2-M/V}V))$
- 노드 1000개에 약 100만번의 union/find연산 → 1000만번 가량 연산 필요
서로소 집합 활용 - 사이클 판별
- 서로소 집합은 무방향 그래프 내에서의 사이클 판별 가능
<aside> 💡 DFS를 이용해서도 가능
</aside>
동작 과정
- 각 간선(union 연산)을 확인하며 두 노드의 루트 노드를 확인
- 루트 노드가 서로 다르면 두 노드에 대해 union 연산을 수행
- 루트 노드가 서로 같다면 사이클(cycle)이 발생한 것
- 그래프에 포함되어 있는 모든 간선에 대해 1번 과정을 반복
동작 예시
초기 단계 : 모든 노드에 대해 자기 자신을 부모로 설정하는 형태로 부모 테이블 초기화
(1, 2) 간선 확인
(1, 3) 간선 확인
(2, 3) 간선 확인
이 때 2와 3이 이미 루트 노드로 ‘노드 1’을 가지고 있음
→ 사이클이 발생함
구현
# 특정 원소가 속한 집합을 찾기
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) # 부모 테이블 초기화
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
parent[i] = i
cycle = False # 사이클 발생 여부
for i in range(e):
a, b = map(int, input().split())
# 사이클이 발생한 경우 종료
if find_parent(parent, a) == find_parent(parent, b):
cycle = True
break
# 사이클이 발생하지 않았다면 합집합 수행
else:
union_parent(parent, a, b)
print('사이클 발생') if cycle else print('사이클 미발생')
크루스칼(Kruskal) 알고리즘
신장 트리 (Spanning Tree)
- 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
- 예)
기본 그래프
신장 트리
신장 트리가 아닌 것들
- 비포함 노드 존재
- 비포함 노드 존재 / 사이클 존재
- 최소 신장 트리 (MST; Mininum Spanning Tree)
신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리
예)
개념 정리
- 가장 적은 비용으로 모든 노드를 연결할 수 있게 해주는 알고리즘
- 최소 신장 트리 알고리즘
- 그리디 알고리즘
- 시간 복잡도
- $O(ElogE)$ (E = 간선의 개수)
- E개의 간선을 정렬하는 작업의 시간 복잡도와 같다고 할 수 있음
- 크루스칼 내부에서 사용되는 서로소 집합 알고리즘 복잡도는 작으므로 무시함
- $O(ElogE)$ (E = 간선의 개수)
동작 과정
- 모든 간선에 대해 정렬을 수행 → 가장 거리가 짧은 간선부터 집합에 포함 (그리디)
- 이 때 사이클을 발생시킬 수 있는 간선의 경우, 집합에 포함시키지 않음
- 간선 데이터를 비용에 따라 오름차순 정렬
- 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인
- 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킴
- 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않음
- 모든 간선에 대해 2번의 과정을 반복
동작 예시
초기 단계 : 그래프의 모든 간선 정보만 빼내어 정렬 수행
- 실제로는 전체 간선 데이터를 리스트에 담은 뒤에 정렬
- 여기서는 가독성을 위해 노드 데이터 순서에 따라 나열함
가장 짧은 간선(3, 4)을 선택해 집합에 포함 (union 실행)
그 다음 작은 간선(4, 7)을 선택 → 4, 7이 같은 집합에 속하는지 확인 (사이클 확인) → union 실행
그 다음 작은 간선(4, 6)을 선택 → 4, 6이 같은 집합에 속하는지 확인 (사이클 확인) → union 실행
그 다음 작은 간선(6, 7)을 선택 → 4, 7이 같은 집합에 속하는지 확인 (사이클 확인) → 이미 동일한 집합에 포함 → union 미실행
그 다음 작은 간선(1, 2)을 선택 → 1, 2이 같은 집합에 속하는지 확인 (사이클 확인) → union 실행
그 다음 작은 간선(2, 6)을 선택 → 2, 6이 같은 집합에 속하는지 확인 (사이클 확인) → union 실행
그 다음 작은 간선(2, 3)을 선택 → 2, 3이 같은 집합에 속하는지 확인 (사이클 확인) → 이미 동일한 집합에 포함 → union 미실행
그 다음 작은 간선(5, 6)을 선택 → 5, 6이 같은 집합에 속하는지 확인 (사이클 확인) → union 실행
그 다음 작은 간선(1, 5)을 선택 → 1, 5이 같은 집합에 속하는지 확인 (사이클 확인) → 이미 동일한 집합에 포함 → union 미실행
최종 최소 신장 트리
- 총 비용 : 최소 신장 트리의 간선을 모두 더한 값
구현
# 특정 원소가 속한 집합을 찾기
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)
입력
7 9
1 2 29
1 5 75
2 3 35
2 6 34
3 4 7
4 6 23
4 7 13
5 6 53
6 7 25
위상 정렬 (Topology Sort)
진입차수(Indegree)
- 특정한 노드로 ‘들어오는’ 간선의 개수
개념 정리
순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘
방향 그래프의 모든 노드를 ‘방향성에 거스르지 않도록 순서대로 나열하는 것’을 의미
현실 세계에서의 위상 정렬 예시
선수과목을 고려한 학습 순서 설정
- 컴공 커리큘럼 : 자료 구조 (선수과목) → 알고리즘 → 고급 알고리즘
그래프상에서 선후 관계가 있다면, 위상 정렬을 수행하여 모든 선후 관계를 지키는 전체 순서를 계산 가능
진입차수
- 자료구조 : 0
- 알고리즘 : 1
- 고급 알고리즘 : 2
시간 복잡도
- $O(V+E)$
- 차례대로 모든 노드를 확인하면서, 해당 노드에서 출발하는 간선을 차례로 제거하는 시간
동작 과정
- 진입차수가 0인 노드를 큐에 넣음
- 큐가 빌 때까지 다음의 과정을 반복
- 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거
- 새롭게 진입차수가 0이 된 노드를 큐에 넣음
- 이때 모든 원소를 방문하기 전에 큐가 빈다면, 사이클이 존재함
- 큐에서 원소가 V번 추출되기 전에 큐가 비어버리면 사이클이 발생한 것임
- 사이클이 존재하는 경우 포함되어 있는 원소 중에서 어떠한 원소도 큐에 들어가지 못하기 때문
- 진입차수가 0이 되지 못함
동작 예시
초기 단계 : 진입 차수가 0인 노드를 큐에 삽입. 현재 노드 1의 진입차수만 0이므로 큐에 1만 삽입
큐에 들어 있는 노드 1을 꺼내고, 노드 1과 연결된 간선들을 제거 → 그러면 새롭게 노드 2와 노드 5의 진입차수가 0이됨 → 따라서 2와 5 큐에 삽입
큐에 들어 있는 노드 2을 꺼내고, 노드 2과 연결된 간선들을 제거 → 그러면 새롭게 노드 3이 진입차수가 0이됨 → 따라서 3을 큐에 삽입
큐에 들어 있는 노드 5을 꺼내고, 노드 5과 연결된 간선들을 제거 → 그러면 새롭게 노드 6이 진입차수가 0이됨 → 따라서 6을 큐에 삽입
큐에 들어 있는 노드 3을 꺼내고, 노드 3과 연결된 간선들을 제거 → 진입차수가 0이되는 노드가 없으므로 그냥 넘어감
큐에 들어 있는 노드 6을 꺼내고, 노드 6과 연결된 간선들을 제거 → 그러면 새롭게 노드 4이 진입차수가 0이됨 → 따라서 4을 큐에 삽입
큐에 들어 있는 노드 4을 꺼내고, 노드 4과 연결된 간선들을 제거 → 그러면 새롭게 노드 7이 진입차수가 0이됨 → 따라서 7을 큐에 삽입
큐에 들어 있는 노드 7을 꺼내고, 노드 7과 연결된 간선들을 제거 → 진입차수가 0이되는 노드가 없으므로 그냥 넘어감
큐가 비었으므로 종료됨
큐에서 나간 순서대로 1 - 2 - 5 - 3 - 6 - 4 - 7 또는 1 - 5 - 2 - 3 - 6 - 4 - 7 이 해가 됨
- 위 과정에서 큐에서 빠져나간 노드를 순서대로 출력하면 그것이 위상 정렬을 수행한 결과가 됨
- 위상 정렬을 수행한 결과의 해는 여러 개가 될 수 있음
- 한 단계에서 큐에 들어가는 원소가 2개 이상인 경우
구현
from collections import deque
# 노드의 개수와 간선의 개수 입력받기
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) # 정점 A에서 B로 이동 가능
# 진입차수를 1 증가
indegree[b] += 1
# 위상 정렬 함수
def topology_sort():
result = [] # 알고리즘 수행 결과를 담을 리스트
q = deque() # 큐 기능을 위한 deque 라이브러리 사용
# 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
for i in range(1, v + 1):
if indegree[i] == 0:
q.append(i)
# 큐가 빌 때까지 반복
while q:
# 큐에서 원소 꺼내기
now = q.popleft()
result.append(now)
# 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
for i in graph[now]:
indegree[i] -= 1
# 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
if indegree[i] == 0:
q.append(i)
#위상 정렬을 수행한 결과 출력
for i in result:
print(i, end=' ')
topology_sort()
입력
7 8
1 2
1 5
2 3
2 6
3 4
4 7
5 6
6 4
문제 풀이
팀 결성
풀이
import sys
input = sys.stdin.readline
def find(p, x):
if p[x] != x:
p[x] = find(p, p[x])
return p[x]
def union(p, a, b):
a = find(p, a)
b = find(p, b)
if a < b:
p[b] = a
else:
p[a] = b
n, m = map(int, input().split())
p = [0] * (n + 1)
for i in range(1, n + 1):
p[i] = i
for i in range(m):
op, a, b = map(int, input().split())
if op == 0:
union(p, a, b)
else:
print('YES') if find(p, a) == find(p, b) else print('NO')
입력
7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1
도시 분할 계획
풀이
import sys
input = sys.stdin.readline
def find(p, x):
if p[x] != x:
p[x] = find(p, p[x])
return p[x]
def union(p, a, b):
a = find(p, a)
b = find(p, b)
if a < b:
p[b] = a
else:
p[a] = b
n, m = map(int, input().split())
p = [i for i in range(n + 1)]
edges = []
for i in range(m):
a, b, c = map(int, input().split())
edges.append((c, a, b))
edges.sort()
result = 0
last_road = 0 # 가장 큰 비용의 신장트리 길을 저장하기 위함
for c, a, b in edges:
if find(p, a) != find(p, b):
union(p, a, b)
result += c
last_road = c
print(result - last_road) # 가장 큰 비용의 신장트리 길을 없애 2개의 마을을 만듬
입력
7 12
1 2 3
1 3 2
3 2 1
2 5 2
3 4 4
7 3 6
5 1 5
1 6 2
6 4 1
6 5 3
4 5 3
6 7 4
커리큘럼
풀이
입력
5
10 -1
10 1 -1
4 1 -1
4 3 1 -1
3 3 -1