서로소 집합 (union find)
서로소 집합이란, 공통되는 부분집합이 존재하지 않는 두 집합을 의미한다. 이 개념을 통해 다루게 될 문제는, 바로 어떤 두 그래프가 서로소 집합 관계인지 확인하는 것이다. 이를 확인하는 알고리즘을 union find 알고리즘이라고 하는데, 각 노드가 같은 부모를 가리키는지 확인하는식의 접근이라고 보면된다. 필자는 이런 상황을 이전에 마주한적이 있다.
전력망을 둘로 나누기 (lv2) (tistory.com)
전력망을 둘로 나누기 (lv2)
문제 설명 n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖
forteqook.tistory.com
바로 위 문제인데, 문제에서는 그래프의 간선하나를 잘랐을 때, 나눠진 각각의 두 그래프 노드들의 개수 차가 최소가 되는 경우를 찾도록 요구하고 있다. 문제 조건에 따라 임의로 간선하나를 제거한 뒤, 노드 1번이 포함되어있는 그래프의 노드 개수를 DFS와 백트래킹을 통해 구하고, 이 값과 원래 그래프의 전체 노드 개수를 이용해서 나눠진 두 그래프의 노드 개수 차를 구했다. 하지만 문제에서 주어진 간선 데이터가 무방향이 전제되어 있기 때문에, 기존에 했듯 "출발->도착"과 같이 방향을 전제한 트리 구조로 데이터를 입력받으면 나중에 간선을 제거할 때 제대로 반영이 되지 않았다. 이 때문에 간선 정보를 받을때 위 링크에서 올려둔 코드와 같이 한번에 두개의 key값을 생성했고, 다소 직관적이지 못한 형태의 코드가 되었다.
이를 말끔하게 해결할 수 있는 방법이 바로 서로소 집합 개념이다. union find 알고리즘에서는 각 노드의 루트 노드를 기록한 테이블을 만들어 각 노드가 어느 집합에 포함되어 있는지 확인한다. 위 문제 같은 경우도, 간선을 임의로 하나씩 제거해보며 서로소 집합을 만든 뒤, 두개의 집합이 나온다면 두 집합의 노드 개수를 비교하면 된다. 그렇다면 union find 알고리즘은 어떤 방식으로 간선정보를 받아 각 노드의 루트노드를 기록할까? 이름처럼 해당 알고리즘은 크게 union과 find 로 이루어져 있다.
- union : 어떤 간선정보를 받아, 두 노드를 (간선 정보에는 두개의 노드가 원소로 들어감) 특정 집합에 포함 시키는 작업. 해당 작업에서 두 노드의 루트노드는 갱신되는데, 보통은 같은 집합 내에 노드의 번호가 가장 작은 노드를 우선시하여 루트 노드로 지정한다.
- find : 특정 노드의 루트노드가 무엇인지 get 하는 작업.
해당 알고리즘은 기본적으로 간선정보를 입력받으며 각 노드의 루트노드 정보를 계속해서 갱신해나간다. find_parent 메서드는 단순히 부모노드가 무엇인지만 리턴하는것이 아니라, 부모 노드를 루트노드로 갱신하여 모든 union연산이 완료된 후에 특정 노드가 어느집합에 속해있는지 바로 찾을 수 있도록 한다. 노드의 개수가 V개로 주어져 최대 V-1 의 union 연산이 발생할 수 있고, M번 만큼의 find 연산이 필요하다고 할 때 해당 알고리즘의 시간 복잡도는 대략 V + MlogV 라고 한다.
# 특정 원소가 속한 집합을 찾기
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=' ')예제
'같은 팀 여부 확인', 즉 find 연산에 대해 결과를 출력해주는 기본적인 union 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
n, m = map(int, input().split())
parent = [0] * (n + 1) # 부모 테이블 초기화
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(0, n + 1):
parent[i] = i
# 각 연산을 하나씩 확인
for i in range(m):
oper, a, b = map(int, input().split())
# 합치합(Union) 연산인 경우
if oper == 0:
union_parent(parent, a, b)
# 찾기(Find) 연산인 경우
elif oper == 1:
if find_parent(parent, a) == find_parent(parent, b):
print('YES')
else:
print('NO')무방향 그래프의 사이클 판별
union find 알고리즘을 활용하여 무방향 그래프가 주어졌을 때 사이클이 발생하는지 판별할 수 있다. 간선정보를 입력받았을 때 두 노드의 루트노드가 같다면 사이클이 발생했다고 판별된다. 다시말해, 입력받은 간선에 대해 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) # 부모 테이블 초기화하기
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
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
# 사이클이 발생하지 않았다면 합집합(Union) 연산 수행
else:
union_parent(parent, a, b)
if cycle:
print("사이클이 발생했습니다.")
else:
print("사이클이 발생하지 않았습니다.")크루스칼 알고리즘
그래프가 주어진 모든 노드를 포함하면서 동시에 사이클이 발생하지 않는다면 이를 신장트리라고 부른다. 크루스칼 알고리즘은 어떤 그래프의 각 간선에 비용이 존재한다고 가정했을때 최소한의 비용으로 신장트리를 찾는 방법을 제시한다. 이는 출발점과 도착점을 딱히 정해놓지 않고 모든 노드를 최소한의 비용으로 방문해야하는 상황에 이용가능하다. 모든 노드를 돌았을 때 비용의 합이 최소가 되려면 가장 간선 비용이 적은것부터 순회하며 사이클이 발생하는지 판별하고, 발생하지 않는다면 union으로 집합에 넣어주면 된다. 간선의 개수가 E개라고 할때, 시간복잡도는 대략 O(ElogE)가 된다. 이는 간선을 비용순서로 정렬하는데 발생하는 비용이다.
# 특정 원소가 속한 집합을 찾기
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)예제
초장에 원숭이는 왜 나왔는지 이해가 안가는 문제지만 (이 문제를 풀고있는 취준생들에 대한 비유일까?) 아무튼 주어진 그래프에서 최소신장트리를 찾고 남아있는 간선 중 하나를 잘랐을 때 합이 최소가 되는 경우를 찾아야하니 그 중 가장 비용이 큰 간선만 잘라주면 되는 문제이다. 전형적인 크루시칼 알고리즘 문제이다.
# 특정 원소가 속한 집합을 찾기
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()
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
print(result - last)위상 정렬
방향 그래프에서 순서에 맞게 모든 노드를 나열하는 정렬이다. 진입차수, 즉 자신을 가리키고 있는 간선의 개수가 0인, 다시말해 부모노드가 없는 노드들 부터 큐에 넣고, 큐에서 해당 노드를 꺼내면서 다시 진입차수가 0이되는 노드들을 큐에 삽입한다. DFS로도 접근이 가능한데, 그래프에서 방문하지 않은 임의의 노드를 선택해서 DFS를 수행하고, 다시 방문하지 않은 다른 노드에 대해 같은 수행을 반복하면서 방문한 노드들을 전부 스택에 담아두는 것이다. 이후 후입선출 방식으로 방문한 노드들을 꺼내면 위상정렬이 된다. 방향 그래프 탐색 문제에서 시작 노드가 반드시 루트노드여야 하는 문제에서 유효한 접근법이라고 생각된다.
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():
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()예제
과목은 동시 수강이 가능하므로, 어떤 과목의 종료시간은 선수 과목들 중 가장 늦게 끝나는 과목의 소요시간에 그 과목의 소요시간을 합한것과 같을 것이다. 문제에서 구현하길 원하는 것은 먼저 선수과목이 아예 없는 과목들을 함께 수강하고, 그 다음 강의들에 대해서도 같은 작업을 반복한다는 점에서, 반드시 루트노드부터 순회해야하는 위상정렬 문제라고 볼 수 있다.
from collections import deque
import copy
# 노드의 개수 입력받기
v = int(input())
# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (v + 1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트(그래프) 초기화
graph = [[] for i in range(v + 1)]
# 각 강의 시간을 0으로 초기화
time = [0] * (v + 1)
# 방향 그래프의 모든 간선 정보를 입력받기
for i in range(1, v + 1):
data = list(map(int, input().split()))
time[i] = data[0] # 첫 번째 수는 시간 정보를 담고 있음
for x in data[1:-1]:
indegree[i] += 1
graph[x].append(i)
# 위상 정렬 함수
def topology_sort():
result = copy.deepcopy(time) # 알고리즘 수행 결과를 담을 리스트
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]:
result[i] = max(result[i], result[now] + time[i])
indegree[i] -= 1
# 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
if indegree[i] == 0:
q.append(i)
# 위상 정렬을 수행한 결과 출력
for i in range(1, v + 1):
print(result[i])
topology_sort()'PS > 이것이 취업을 위한 코딩 테스트다 with 파이썬' 카테고리의 다른 글
| 볼링공 고르기 - 그리디 (0) | 2022.07.27 |
|---|---|
| 만들 수 없는 금액 - 그리디 (0) | 2022.07.27 |
| 모험가 길드 - 그리디 (0) | 2022.07.27 |
| 편집 거리 - DP (0) | 2022.07.25 |
| 못생긴 수 - DP (0) | 2022.07.24 |