다양한 그래프 알고리즘
들어가기 전에…
- 우선, 앞서 공부했던 그래프에 대해 복습해보도록 하자.
- 그래프란, 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조이다.
- 주로 ‘서로 다른 객체가 연결되어 있다~’라는 식의 문제가 출제된다.
- 트리란, 부모에서 자식으로 내려오는 계층적인 모델에 속한다.
- 컴퓨터 공학에서는 보통 방향 그래프라고 간주된다.
- 그래프 구현 방법에는 인접 행렬(2차원 행렬을 사용)과 인접 리스트(리스트 사용)가 있다.
- 노드의 개수가 V, 간선의 개수가 E인 그래프에서, 시-공간 복잡도는 아래와 같다.
복잡도 인접 행렬 인접 리스트 시간 O(1) O(V^2) 공간 O(V) O(E) 알고리즘 플로이드-워셜 다익스트라 - 즉, 노드의 개수가 적은 경우에는 플로이드 워셜 알고리즘을, 노드-간선 개수 많으면 우선순위 큐를 적용한 다익스트라 알고리즘을 적용하면 된다.
- 그래프란, 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조이다.
- 이제, 이 외의 그래프 알고리즘을 알아보도록 하자.
서로소 집합
- 서로소 집합은 공통 원소가 없는 두 집합을 의미한다.
- 이를 응용하려면 서로소 집합 자료구조가 있어야 하는데, 이는 서로소 부분 집합들로 나눠진 원소들의 데이터를 처리하기 위한 자료구조라 할 수 있다.
-
서로소 집합 자료구조는 union(합집합), find(찾기: 특정한 원소가 속한 집합이 뭔지 알려주는 연산) 두 개의 연산으로 조작할 수 있다. 그래서 union-find 자료구조라고도 한다.
#### 서로소 집합 자료구조
- 서로소 집합 자료구조를 표현할 때는 앞서 설명한 트리 자료구조를 사용하는데, 해당 알고리즘은 다음과 같다.
- union 연산을 확인해, 서로 연결된 두 노드 A, B를 확인한다. A, B의 루트 노드 A’, B’를 각각 찾고, A’를 B’의 부모로 설정해 B’가 A’를 가리키도록 한다.
- 모든 union 연산을 처리할 때까지 1.과정을 반복한다.
- 서로소 집합 자료구조를 표현할 때는 앞서 설명한 트리 자료구조를 사용하는데, 해당 알고리즘은 다음과 같다.
# 특정 원소가 속한 집합을 찾기
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=' ')
- 이 알고리즘의 전체 시간 복잡도는 O(VM)이라 비효율적.
-
find 함수는 ‘경로 압축’기법을 통해 시간 복잡도 측면에서의 최적화가 가능하다.
- 경로 압축(path compression)은 find 함수를 재귀적으로 호출한 뒤 부모 테이블 값을 갱신하는 기법이다.
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
- 이렇게 함수를 수정하면 각 노드에 대해 find 함수를 호출한 이후, 해당 노드의 루트 노드가 바로 부모 노드가 된다.
- 그러면, 이걸 응용하는 방법으로 ‘사이클 판별’을 보도록 하자.
- 원리는 단순하다. 서로 다른 두 노드가 연결되어 있을 때, 두 노드가 똑같은 부모 노드를 가지게 되면 사이클이라고 판단한다.
# 특정 원소가 속한 집합을 찾기, 경로 압축 적용
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 # cycle 발생 여부
# union 연산을 각각 수행
for i in range(e):
a, b = map(int, input().split())
# cycle이 발생하면 바로 종료
if find_parent(parent, a) == find_parent(parent, b):
cycle = True
break
else:
union_parent(parent, a, b)
# 사이클 발생 여부 출력
if cycle:
print("cycle occured")
else:
print("cycle didn't occured")
신장 트리(Spanning Tree)
-
신장 트리는 하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다.
-
신장 트리 여부를 판단하는 알고리즘이 바로 크루스칼 알고리즘이다.
크루스칼 알고리즘
- 크루스칼 알고리즘은, 가능한 한 최소한의 비용으로 신장 트리를 찾을 때 사용된다.
- 원리는 아래와 같다.
- 가장 거리가 짧은 간선부터 차례대로 집합에 추가한다
- 사이클을 발생시키는 간선은 제외하고 연결한다.
- 신장 트리에 포함되어 있는 간선의 비용을 모두 더하면, 그 값이 최종 비용에 해당한다.
- 코드를 보면서 이해해보도록 하자.
```python
특정 원소가 속한 집합을 찾기, 경로 압축 적용
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
edges = [] result = 0 # 부모 테이블상에서, 부모를 자기 자신으로 초기화
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)
- 크루스칼 알고리즘의 시간 복잡도는 O(ElogE)이다. 왜냐하면 크루스칼 알고리즘에서 시간이 가장 오래 걸리는 부분이 간선을 정렬하는 작업이기 때문이다.
___
## 위상 정렬(Topology Sort)
- 위상정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다.
- 즉, **방향** 그래프의 모든 노드를 방향성에 거스르지 안도록 순서대로 나열하는 것을 의미한다.
- 진입차수(Indegree): 특정한 노드로 '들어오는' 간선의 개수를 의미
위상 정렬의 원리는 다음과 같다.
1. 진입차수가 0인 노드를 큐에 넣는다(시작지점)
2. 큐가 빌 때까지 다음의 과정을 반복한다.
* 큐에서 원소를 꺼내, 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
* 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
코드를 통해 이해해보도록 하자.
```python
from collections import deque # 큐를 가져옴
# 노드의 개수와 간선의 개수 입력받기
v, e = map(int, input().split())
# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (v+1)
# 각 노드에 연결된 간선 정보를 담기 위한 연걸 리스트(그래프) 초기화
graph = [[] for i 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(indegree):
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(indegree)
딱 봤을 때는 감이 잘 안올 것이다. 문제를 풀면서 그래프 알고리즘을 익혀보자.
문제
문제 1
학교에서 학생들에게 0번부터 N번까지 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어 총 N+1개의 팀이 존재한다. 이때 선생님은 '팀 합치기' 연산과 '같은 팀 여부 확인' 연산을 사용할 수 있다.
1. '팀 합치기' 연산은 두 팀을 합치는 연산이다.
2. '같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다.
선생님이 M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인' 연산에 대한 연산 결과를 출력하는 프로그램을 작성하시오.
# 입력 조건
* 첫째 줄에는 N, M이 주어진다. 다음 줄부터는 각각의 연산이 주어진다.
* '팀 합치기' 연산은 '0 a b'형태로 주어진다. a번이 속한 팀과 b번이 속한 팀을 합친다는 의미다.
* '같은 팀 여부 확인'은 '1 a b'형태로 주어진다. 두 학생이 같은 팀에 속했는 지 확인하는 연산이다. 이 연산에 대해서, 한 줄에 하나씩 NO/YES를 출력한다.
- ‘같은 팀’에서, ‘서로소 집합’ 문제임을 바로 알 수 있다. 서로소 집합 코드를 이용하여 바로 풀어보도록 하자.
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
# 노드의 개수와 연산의 개수 입력받기
n, m = map(int, input().split())
parent = [0] * (n + 1)
# 부모 테이블 상에서, 부모를 자기 자신으로 초기화
for i in range(1, n+1):
parent[i] = i
li = [] # 출력용 리스트
# 연산을 각각 수행
for i in range(m):
k, a, b = map(int, input().split())
if k == 0: # 합치기 연산이라면
union_parent(parent, a, b)
else: # 검색 연산이라면
if find_parent(parent, a) == find_parent(parent, b): # 같은 팀이면
li.append('YES')
else: # 아니면
li.append('NO')
for i in li:
print(i)
문제 2: 도시 분할 계획
마을은 N개의 집과 M개의 길로 이루어져 있다. 마을을 2개의 분리된 마을로 분할하고자 하는데, 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다.
또한, 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있고, 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다.
마을을 분리하는 김에 불필요한 길을 모두 없애버리려는 셈이다!...아무튼, 이것을 구하는 프로그램을 작성하시오.
# 입력조건
1. 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다.
2. 다음 줄부터 A, B, C 3개의 정수로 공백으로 구분되어 주어지는데, A번 집과 B번 집을 연결하는 길의 유지비가 C라는 뜻이다.
# 출력조건
길을 없애고 남은 유지비 합의 최솟값을 출력한다.
- ‘유지비’… ‘비용’… 이것은 위에서 다룬 크루스칼 알고리즘임을 파악할 수 있다. ‘마을을 둘로 나눈다’는 점에 유의해서 코드를 작성해보자. 뭐… 둘로 나누는 것은 생각보다 어렵지 않을 것이다.
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
edges = []
result = 0 # 부모 테이블상에서, 부모를 자기 자신으로 초기화
for _ in range(e): # 모든 간선에 대한 정보를 입력받기
a, b, cost = map(int, input().split())
# 비용 순으로 정렬하기 위해서 튜플의 첫 번째 원소를 비용으로 설정
edges.append((cost, a, b))
# 간선을 비용순으로 정렬
edges.sort()
last = 0 # 변수!
# 간선을 하나씩 확인하며
for edge in edges:
cost, a, b = edge
# 사이클이 발생하지 않는 경우에만 집합에 포함
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
result += cost
last = cost # 길의 유지비를 last에 기록.
# 그냥 가장 비싼 유지비가 드는 길을 끊어버리자!
result -= last
print(result)
- 어렵지 않게, 크루스칼 알고리즘을 수행한 후의 그래프에서, 가장 비용이 비싼 간선을 끊어서 문제를 해결하였다.
- edges는 비용 순으로 정렬되었기 때문에, last에는 ‘크루스칼의 결과’에 해당하는 cost 중 가장 비싼 값이 기록되게 된다.
문제 3: 커리큘럼
이번 여름방학에는 N개의 강의를 들어야지!! 그런데, 각 강의마다 '선수 강의'가 정해져 있다!!
모든 강의는 1번부터 N번까지의 번호를 가진다. 또한, 동시에 여러 개의 강의를 들을 수 있다고 가정한다. 이때, '여러개의 선수 강의'가 있다면, 모두 들어야 강의를 들을 수 있다.
* 입력 조건:
1. 첫째 줄에 듣고자 하는 강의의 수 N이 주어진다.
2. 다음부터, 각 강의의 강의 시간과 그 강의를 듣기 위해 먼저 들어야 하는 강의들의 번호가 자연수로 주어지며, 각 자연수는 공백으로 구분한다.
3. 각 강의번호는 1부터 N까지로 구성되며, 각 줄은 -1로 끝난다.
예시)
5 # 강의는 5개
10 -1 # 첫번째 강의는 10시간 걸린다
10 1 -1 # 두번째 강의는 10시간 걸리고, 1번 강의를 들어야 한다
4 1 -1 # 세번째 강의는 4시간 걸리고, 1번 강의를 들어야 한다
4 3 1 -1 # 네번째 강의는 4시간 걸리고, 1번과 3번 강의를 들어야 한다
3 3 -1 # 마지막 강의는 3시간 걸리고, 3번 강의를 들어야 한다.
* 출력 조건:
* N개의 강의애 대해 수강하기까지 걸리는 최소 시간을 한 줄에 하나씩 출력한다.
10
20
14
18
17
- ‘강의’는 ‘선수 강의’라는 게 존재하기 때문에, 방향이 정해져 있는 ‘위상 정렬’을 이용해야 한다. ‘동시에 여러 강의를 들을 수 있다’는 점에 유의하도록 하자.
from collections import deque # 큐를 가져옴
import copy
# 노드의 개수 입력받기
v = int(input())
# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (v+1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트(그래프) 초기화
graph = [[] for i in range(v + 1)]
# 각 강의를 듣는 시간(비용)을 담을 리스트 추가
cost = [0] * (v + 1)
# 방향 그래프의 모든 간선 정보를 입력받기
for node in range(v):
li = list(map(int, input().split()))
for i in range(len(li) - 1):
if i == 0:
cost[node + 1] = li[i] # 비용 입력받기
else:
graph[li[i]].append(node + 1) # 정점 li[i]에서 node로 이동
# 진입차수를 1 증가
indegree[node + 1] += 1
# 위상 정렬 함수
def topology_sort(indegree, v):
result = copy.deepcopy(cost) # 알고리즘 수행 결과를 담을 리스트
q = deque() # 큐 기능을 위한 deque 라이브러리 사용
# 처음 시작할때는 진입차수가 0인 노드를 큐에 삽입
for i in range(1, v+1):
if indegree[i] == 0:
q.append(i)
# 큐가 빌 때까지 반복
while q:
# 큐에서 원소 꺼내기
now = q.popleft()
# 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
for i in graph[now]:
indegree[i] -= 1
result[i] = max(result[i], (cost[i] + result[now])) # 더 비용이 적은 케이스 계산
# 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
if indegree[i] == 0:
q.append(i)
# 위상 정렬을 수행한 결과 출력
for i in range(1, len(result)):
print(result[i])
# 위상 정렬 함수 실행
topology_sort(indegree, v)
-
max를 이용해서, 수강 시간이 더 오래 걸리는 경우를 찾으면 된다.
-
여기까지, 그래프 이론에 대하여 공부하였다.