코딩 테스트에서 자주 등장하는 기타 그래프 이론 공부하기
그래프 | 트리 | |
---|---|---|
뱡향성 | 방향 그래프 혹은 무방향 그래프 | 방향 그래프 |
순환성 | 순환 및 비순환 | 비순환 |
루트 노드 존재 여부 | 루트 노드가 없음 | 루트 노드가 존재 |
노드 간 관계성 | 부모와 자식 관계 없음 | 부모와 자식 관계 |
모델의 종류 | 네트워크 모델 | 계층 모델 |
서로소 집합
서로소 집합 자료구조
서로소 집합 알고리즘
def find_parent(parent, x) :
# 루트 노드가 아닌 경우, 루트 노드를 찾을 때까지 재귀 호출
if parent[x] != x :
return find_parent(parent, parent[x])
return x
# 두 원소가 속한 집합 union
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
v, e = map(int, input().split()) # 노드, 간선 개수
parent = [0] * (v + 1) # 부모 테이블 초기화
for i in range(1, v + 1) :
parent[i] = i
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 = ' ')
개선된 서로소 집합 알고리즘
def find_parent(parent, x) :
# 루트 노드가 아닌 경우, 루트 노드를 찾을 때까지 재귀 호출
if parent[x] != x :
parent[x] = find_parent(parent, parent[x])
return parent[x]
# 두 원소가 속한 집합 union
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
v, e = map(int, input().split()) # 노드, 간선 개수
parent = [0] * (v + 1) # 부모 테이블 초기화
for i in range(1, v + 1) :
parent[i] = i # 부모를 자기 자신으로 초기화
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 = ' ')
서로소 집합을 활용한 사이클 판별
def find_parent(parent, x) :
# 루트 노드가 아닌 경우, 루트 노드를 찾을 때까지 재귀 호출
if parent[x] != x :
parent[x] = find_parent(parent, parent[x])
return parent[x]
# 두 원소가 속한 집합 union
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
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)
if cycle :
print('사이클 발생')
else :
print('사이클이 발생하지 않음')
신장 트리
하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미
크루스칼 알고리즘 [그리디 알고리즘]
def find_parent(parent, x) :
# 루트 노드가 아닌 경우, 루트 노드를 찾을 때까지 재귀 호출
if parent[x] != x :
parent[x] = find_parent(parent, parent[x])
return parent[x]
# 두 원소가 속한 집합 union
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
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)
위상 정렬
from collections import deque
v, e = map(int, input().split()) # 노드, 간선 개수
indegree = [0] * (v + 1) # 모든 노드 진입차수 0
graph = [[] for i in range(v + 1)] # 연결 리스트 (그래프)
# 방향 그래프의 모든 간선 정보 입력
for _ in range(e) :
a, b = map(int, input().split())
graph[a].append(b) # 정점 a에서 b로 이동
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()
팀 결성
💡 서로소 집합 알고리즘
def find_parent(parent, x) :
# 루트 노드가 아닌 경우, 루트 노드를 찾을 때까지 재귀 호출
if parent[x] != x :
parent[x] = find_parent(parent, parent[x])
return parent[x]
# 두 원소가 속한 집합 union
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 # 부모를 자기 자신으로 초기화
for i in range(m) :
oper, a, b = map(int, input().split())
# 합잡합 연산인 경우
if oper == 0 :
union_parent(parent, a, b)
# 찾기 연산인 경우
elif oper == 1 :
if find_parent(parent, a) == find_parent(parent, b) :
print('YES')
else :
print("NO")
도시 분할 계획
💡 전체 그래프에서 2개의 최소 신장 트리 생성
💡 크루스칼 알고리즘으로 최소 신장 트리 구성 간선 중 비용이 큰 간선 제거
def find_parent(parent, x) :
# 루트 노드가 아닌 경우, 루트 노드를 찾을 때까지 재귀 호출
if parent[x] != x :
parent[x] = find_parent(parent, parent[x])
return parent[x]
# 두 원소가 속한 집합 union
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
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)
커리큘럼
💡 위상 정렬 알고리즘
from collections import deque
import copy
v = int(input()) # 노드의 개수
indegree = [0] * (v + 1) # 모든 노드의 진입차수 0 초기화
graph = [[] for i in range(v + 1)] # 간선 정보 리스트 초기화
time = [0] * (v + 1) # 시간 0으로 초기화
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 -= 1
# 새롭게 진입차수 0이되는 노드 큐에 삽입
if indegree[i] == 0 :
q.append(i)
for i in range(1, v + 1) :
print(result[i])
topology_sort()