Yu's Algolithm Note

글 작성

제목과 내용을 간결하게 정리해 주세요.

제목

내용

<h2>지금까지의 그래프 알고리즘 및 이론 정리</h2><h3>그래프(Graph) 요약</h3><ul><li>구성요소<ul><li>노드(Node) / 정점(Vertex)</li><li>간선(Edge)</li></ul></li><li>프로그래밍 언어에서 그래프 표현 방법<ul><li>인접 행렬</li><li>인접 리스트</li></ul></li></ul><h3>DFS/BFS → <a href="https://www.notion.so/DFS-BFS-Graph-Traversal-5fd3669c15254f6cb5c8e662f72e637d?pvs=21">DFS/BFS (Graph Traversal)</a></h3><ul><li>DSF<ul><li>스택(재귀)을 이용한 그래프 탐색</li></ul></li><li>BFS<ul><li>큐를 이용한 그래프 탐색</li></ul></li></ul><h3>최단 경로 → <a href="https://www.notion.so/Shortest-Path-e7e4d3e1da2f40028273dff5cc99246d?pvs=21">최단 경로 (Shortest Path)</a></h3><ul><li>단일 쌍의 최단거리<ul><li>다익스트라<ul><li>그리드</li><li>인접 리스트</li></ul></li></ul></li><li>모든 쌍의 최단거리<ul><li>플루이드 워셜<ul><li>다이나믹 프로그래밍</li><li>인접 행렬</li></ul></li></ul></li></ul><h3>트리</h3><ul><li>그래프의 한 종류</li><li>부모에서 자식으로 내려오는 계층적 모델</li><li>전통적인 수학에서는 무방향 그래프로 간주되지만, 컴퓨터공학 분야에서는 보통 방향 그래프라고 간주</li><li>$간선의 개수 = 노드의 개수-1$ 인 특징을 가짐</li></ul><h3>그래프와 트리 비교</h3><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/b82d319e-6a21-4196-848c-b03148362381/Untitled.png" alt="Untitled"><h2>전체 윤곽 보고가기</h2>서로소 집합 자료구조에 대해 알아봄→ 무방향 그래프에서의 사이클(순환) 여부 판별에 활용할 수 있음→ 최소 신장 트리를 구하기 위한 크루스칼 알고리즘에 활용위상 정렬에 대해 알아봄<h2>서로소 집합 (Disjoint Sets) 자료구조</h2><h3>서로소 집합</h3><ul><li>공통 원소가 없는 두 집합을 의미<ul><li>예) 집합 {1, 2}와 {3, 4}는 서로소 관계</li></ul></li></ul><h3>서로소 집합 자료구조 (union-find)</h3>서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조연산 종류<ul><li>union (합집합) : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산</li><li>find (찾기) : 특정한 원소가 속한 집합이 어떤 집합인지(루트 노드가 무엇인지) 알려주는 연산</li></ul>구현 방법<pre><code class="language-python">1. union 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인
 i . A와 B의 루트 노드 A’, B’를 각각 찾음
 ii. A’를 B’의 부모 노드로 설정 (B’가 A’를 가리키도록 함)
2. 모든 union 연산을 처리할 때까지 1번 과정을 반복
</code></pre><ul><li>트리 자료구조 이용</li><li>A’와 B’ 중에 더 번호가 작은 원소가 부모 노드가 되도록 구현하는 경우가 많음</li><li>’가리킨다‘는 의미는 부모 노드로 설정한다는 것</li></ul><h3>동작 예시</h3><ul><li>전체 집합 {1, 2, 3, 4, 5, 6}</li><li>연산<ul><li>union 1, 4 → 1과 4는 같은 집합 의미</li><li>union 2, 3 → 2과 3는 같은 집합 의미</li><li>union 2, 4 → 2과 4는 같은 집합 의미</li><li>union 5, 6 → 5과 6는 같은 집합 의미</li></ul></li><li>동작 방식<ul><li>union연산을 하나씩 확인(루프) → 서로 다른 두 원소에 대해 합집합을 수행 (각각 루트 노드를 찾아서 더 큰 루트 노드가 더 작은 루트 노드를 가리키도록 설정)</li></ul></li></ul>가장 먼저 노드의 개수(V) 크기의 부모 테이블 초기화<ol><li>자기 자신을 부모로 갖도록 초기화</li><li>부모 테이블은 해당 노드의 부모에 대한 정보만을 가짐<ol><li>루트 노드 확인을 위해서는 재귀적으로 부모를 거슬러 올라가 최종적인 루트 노드를 찾아야함</li></ol></li></ol>union 1, 4 : 1과 4를 합침1과 4의 루트 노드를 각각 찾아 (현재는 각각 1과 4) 더 큰 번호에 해당하는 루트 노드 4의 부모를 1로 설정<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/32615979-9b89-47f4-8591-08cda63310bb/Untitled.png" alt="Untitled">union 2, 3 : 2와 3을 합침2와 3의 루트 노드를 각각 찾아 (현재 각각 2와 3) 더 큰 번호에 해당하는 루트 노드 3의 부모를 2로 설정<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/cc1087da-a2b2-4853-8e55-17d51dba5439/Untitled.png" alt="Untitled">union 2, 4 : 2와 4를 합침2와 4의 루트 노드를 각각 찾아 (현재 각각 2와 1) 더 큰 번호에 해당하는 루트 노드 2의 부모를 1로 설정<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/5f880ad4-8937-4162-bb25-afa1d72017dc/Untitled.png" alt="Untitled"><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/94d9436b-1304-48cf-a6fc-7a34fcf0d614/Untitled.png" alt="Untitled">union 5, 6 : 5와 6을 합침5와 6의 루트 노드를 각각 찾아 (현재 각각 5와 6) 더 큰 번호에 해당하는 루트 노드 6의 부모를 5로 설정<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/93da9572-2221-44e4-a9f5-1d40c202b1d2/Untitled.png" alt="Untitled">union 연산 모두 완료<ul><li>위 과정에서 유의할 점<ul><li>union연산을 효과적으로 수행하기 위해 ‘부모 테이블’을 항상 가지고 있어야 함</li><li>루트 노드를 즉시 계산할 수 없고, 부모 테이블을 거슬러 올라가야 함</li></ul></li></ul><h3>구현</h3>기본적인 서로소 집합 알고리즘<pre><code class="language-python"># 특정 원소가 속한 집합 찾기
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 &lt; 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()
</code></pre>경로 압축 기법을 적용한 서로소 집합 알고리즘<pre><code class="language-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 &lt; 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()
</code></pre>기본적인 서로소 집합 알고리즘의 문제점<ul><li><code>find</code> 함수가 비효율적으로 동작함<ul><li><code>find</code> 시 최악의 경우 $O(V)$가 될 수 있음 → 전체 시간 복잡도가 $O(VM)$ (M: union 연산 개수) 가 될 수 있음</li></ul></li></ul>경로 압축 (Path Compression) 기법 적용<ul><li><code>find</code> 함수를 재귀적으로 호출한 뒤에 부모 테이블의 값을 갱신하는 기법</li><li>각 노드에 대해 <code>find</code> 함수를 호출한 이후에, 해당 노드의 루트 노드가 바로 부모 노드가 되어 시간 복잡도가 개선됨</li><li>시간 복잡도 : $O(V+M(1+log_{2-M/V}V))$<ul><li>노드 1000개에 약 100만번의 union/find연산 → 1000만번 가량 연산 필요</li></ul></li></ul><h3>서로소 집합 활용 - 사이클 판별</h3><ul><li>서로소 집합은 무방향 그래프 내에서의 사이클 판별 가능</li></ul>&lt;aside&gt; 💡 DFS를 이용해서도 가능&lt;/aside&gt;동작 과정<ol><li>각 간선(union 연산)을 확인하며 두 노드의 루트 노드를 확인<ol><li>루트 노드가 서로 다르면 두 노드에 대해 union 연산을 수행</li><li>루트 노드가 서로 같다면 사이클(cycle)이 발생한 것</li></ol></li><li>그래프에 포함되어 있는 모든 간선에 대해 1번 과정을 반복</li></ol>동작 예시초기 단계 : 모든 노드에 대해 자기 자신을 부모로 설정하는 형태로 부모 테이블 초기화<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/eef021e3-00f7-4257-8114-0b0f981b2bce/Untitled.png" alt="Untitled">(1, 2) 간선 확인<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/9eeb45e2-3501-4c30-af60-36f23b573460/Untitled.png" alt="Untitled">(1, 3) 간선 확인<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/d8e66398-8c62-4b37-965e-4c39a0601c29/Untitled.png" alt="Untitled">(2, 3) 간선 확인<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/401ecfdd-c3cc-4276-bcec-df14eb6c95a6/Untitled.png" alt="Untitled">이 때 2와 3이 이미 루트 노드로 ‘노드 1’을 가지고 있음→ 사이클이 발생함구현<pre><code class="language-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 &lt; 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('사이클 미발생')
</code></pre><h2>크루스칼(Kruskal) 알고리즘</h2><h3>신장 트리 (Spanning Tree)</h3><ul><li>하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프</li><li>예)</li></ul>기본 그래프<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/4edf61ec-de80-4118-840b-24ddaf41b01e/Untitled.png" alt="Untitled">신장 트리<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/725138ed-1848-4200-9f4b-231f2070a8da/Untitled.png" alt="Untitled">신장 트리가 아닌 것들<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/aac1d0f5-7ea6-438d-be8d-98011a31fb63/Untitled.png" alt="Untitled"><ul><li>비포함 노드 존재</li><li>비포함 노드 존재 / 사이클 존재</li><li>최소 신장 트리 (MST; Mininum Spanning Tree)</li></ul>신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리예)<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/aad87b0a-c4b3-4db2-8933-a469ea11d9c4/Untitled.png" alt="Untitled"><h3>개념 정리</h3><ul><li>가장 적은 비용으로 모든 노드를 연결할 수 있게 해주는 알고리즘<ul><li>최소 신장 트리 알고리즘</li><li>그리디 알고리즘</li></ul></li><li>시간 복잡도<ul><li>$O(ElogE)$ (E = 간선의 개수)<ul><li>E개의 간선을 정렬하는 작업의 시간 복잡도와 같다고 할 수 있음</li><li>크루스칼 내부에서 사용되는 서로소 집합 알고리즘 복잡도는 작으므로 무시함</li></ul></li></ul></li></ul><h3>동작 과정</h3><ul><li>모든 간선에 대해 정렬을 수행 → 가장 거리가 짧은 간선부터 집합에 포함 (그리디)</li><li>이 때 사이클을 발생시킬 수 있는 간선의 경우, 집합에 포함시키지 않음</li></ul><ol><li>간선 데이터를 비용에 따라 오름차순 정렬</li><li>간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인<ol><li>사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킴</li><li>사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않음</li></ol></li><li>모든 간선에 대해 2번의 과정을 반복</li></ol><h3>동작 예시</h3>초기 단계 : 그래프의 모든 간선 정보만 빼내어 정렬 수행<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/a03622a8-c1ef-4a8f-b5cd-34386120c9be/Untitled.png" alt="Untitled"><ul><li>실제로는 전체 간선 데이터를 리스트에 담은 뒤에 정렬</li><li>여기서는 가독성을 위해 노드 데이터 순서에 따라 나열함</li></ul>가장 짧은 간선(3, 4)을 선택해 집합에 포함 (union 실행)<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/347f1433-6949-44bb-bec4-cb48830419e5/Untitled.png" alt="Untitled">그 다음 작은 간선(4, 7)을 선택 → 4, 7이 같은 집합에 속하는지 확인 (사이클 확인) → union 실행<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/78f851b5-66af-437f-9abb-acd31ef45286/Untitled.png" alt="Untitled">그 다음 작은 간선(4, 6)을 선택 → 4, 6이 같은 집합에 속하는지 확인 (사이클 확인) → union 실행<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/47ab4a06-530c-482c-9472-2708b7fa07e6/Untitled.png" alt="Untitled">그 다음 작은 간선(6, 7)을 선택 → 4, 7이 같은 집합에 속하는지 확인 (사이클 확인) → 이미 동일한 집합에 포함 → union 미실행<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/c0887fb8-b933-4db0-adce-3c2cbdaea0a4/Untitled.png" alt="Untitled">그 다음 작은 간선(1, 2)을 선택 → 1, 2이 같은 집합에 속하는지 확인 (사이클 확인) → union 실행<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/aa57e57d-358a-4d6f-80d8-8d7bd43515b4/Untitled.png" alt="Untitled">그 다음 작은 간선(2, 6)을 선택 → 2, 6이 같은 집합에 속하는지 확인 (사이클 확인) → union 실행<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/527efb3f-4f08-4d46-9532-a3ec6bf104d6/Untitled.png" alt="Untitled">그 다음 작은 간선(2, 3)을 선택 → 2, 3이 같은 집합에 속하는지 확인 (사이클 확인) → 이미 동일한 집합에 포함 → union 미실행<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/f23a4a03-8219-4145-86a5-fd3826a16c47/Untitled.png" alt="Untitled">그 다음 작은 간선(5, 6)을 선택 → 5, 6이 같은 집합에 속하는지 확인 (사이클 확인) → union 실행<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/6dc7b0c4-cc97-435a-94c8-276ab50432d5/Untitled.png" alt="Untitled">그 다음 작은 간선(1, 5)을 선택 → 1, 5이 같은 집합에 속하는지 확인 (사이클 확인) → 이미 동일한 집합에 포함 → union 미실행<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/de99244a-4d66-425b-be32-9634f150fcc0/Untitled.png" alt="Untitled">최종 최소 신장 트리<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/e6a38a4e-a9f5-4495-bad2-4513e7cfd5f1/Untitled.png" alt="Untitled"><ul><li>총 비용 : 최소 신장 트리의 간선을 모두 더한 값</li></ul><h3>구현</h3><pre><code class="language-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 &lt; 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)
</code></pre>입력<pre><code class="language-python">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
</code></pre><h2>위상 정렬 (Topology Sort)</h2><h3>진입차수(Indegree)</h3><ul><li>특정한 노드로 ‘들어오는’ 간선의 개수</li></ul><h3>개념 정리</h3>순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘방향 그래프의 모든 노드를 ‘방향성에 거스르지 않도록 순서대로 나열하는 것’을 의미현실 세계에서의 위상 정렬 예시선수과목을 고려한 학습 순서 설정<ul><li>컴공 커리큘럼 : 자료 구조 (선수과목) → 알고리즘 → 고급 알고리즘</li></ul>그래프상에서 선후 관계가 있다면, 위상 정렬을 수행하여 모든 선후 관계를 지키는 전체 순서를 계산 가능<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/bae07ae5-90aa-4503-8dbe-43c008a2992e/Untitled.png" alt="Untitled">진입차수<ul><li>자료구조 : 0</li><li>알고리즘 : 1</li><li>고급 알고리즘 : 2</li></ul>시간 복잡도<ul><li>$O(V+E)$<ul><li>차례대로 모든 노드를 확인하면서, 해당 노드에서 출발하는 간선을 차례로 제거하는 시간</li></ul></li></ul><h3>동작 과정</h3><ol><li>진입차수가 0인 노드를 큐에 넣음</li><li>큐가 빌 때까지 다음의 과정을 반복<ol><li>큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거</li><li>새롭게 진입차수가 0이 된 노드를 큐에 넣음</li></ol></li></ol><ul><li>이때 모든 원소를 방문하기 전에 큐가 빈다면, 사이클이 존재함<ul><li>큐에서 원소가 V번 추출되기 전에 큐가 비어버리면 사이클이 발생한 것임</li><li>사이클이 존재하는 경우 포함되어 있는 원소 중에서 어떠한 원소도 큐에 들어가지 못하기 때문<ul><li>진입차수가 0이 되지 못함</li></ul></li></ul></li></ul><h3>동작 예시</h3><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/48a89cf3-f42e-4c4e-89c3-d148204cd8d1/Untitled.png" alt="Untitled">초기 단계 : 진입 차수가 0인 노드를 큐에 삽입. 현재 노드 1의 진입차수만 0이므로 큐에 1만 삽입<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/71516205-f844-4714-9ed9-ec0693faab05/Untitled.png" alt="Untitled">큐에 들어 있는 노드 1을 꺼내고, 노드 1과 연결된 간선들을 제거 → 그러면 새롭게 노드 2와 노드 5의 진입차수가 0이됨 → 따라서 2와 5 큐에 삽입<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/64b2e635-894a-42bc-9b22-72661e836056/Untitled.png" alt="Untitled">큐에 들어 있는 노드 2을 꺼내고, 노드 2과 연결된 간선들을 제거 → 그러면 새롭게 노드 3이 진입차수가 0이됨 → 따라서 3을 큐에 삽입<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/53dbf0a2-8ec5-4f28-9215-4badf61f98f5/Untitled.png" alt="Untitled">큐에 들어 있는 노드 5을 꺼내고, 노드 5과 연결된 간선들을 제거 → 그러면 새롭게 노드 6이 진입차수가 0이됨 → 따라서 6을 큐에 삽입<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/b0c9908b-bae5-404d-b025-160bcc1001d8/Untitled.png" alt="Untitled">큐에 들어 있는 노드 3을 꺼내고, 노드 3과 연결된 간선들을 제거 → 진입차수가 0이되는 노드가 없으므로 그냥 넘어감<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/deecd8de-f66f-4d41-9095-ccb75935aaa1/Untitled.png" alt="Untitled">큐에 들어 있는 노드 6을 꺼내고, 노드 6과 연결된 간선들을 제거 → 그러면 새롭게 노드 4이 진입차수가 0이됨 → 따라서 4을 큐에 삽입<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/01a7480e-2318-4cb1-b41f-649a537cdbf4/Untitled.png" alt="Untitled">큐에 들어 있는 노드 4을 꺼내고, 노드 4과 연결된 간선들을 제거 → 그러면 새롭게 노드 7이 진입차수가 0이됨 → 따라서 7을 큐에 삽입<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/c31d81c4-63d8-4a93-80c7-96057d054e8c/Untitled.png" alt="Untitled">큐에 들어 있는 노드 7을 꺼내고, 노드 7과 연결된 간선들을 제거 → 진입차수가 0이되는 노드가 없으므로 그냥 넘어감<img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/b4d51fd5-c922-4f62-a502-15005557c9d3/Untitled.png" alt="Untitled">큐가 비었으므로 종료됨큐에서 나간 순서대로 <code>1 - 2 - 5 - 3 - 6 - 4 - 7</code> 또는 <code>1 - 5 - 2 - 3 - 6 - 4 - 7</code> 이 해가 됨<ul><li>위 과정에서 큐에서 빠져나간 노드를 순서대로 출력하면 그것이 위상 정렬을 수행한 결과가 됨</li><li>위상 정렬을 수행한 결과의 해는 여러 개가 될 수 있음<ul><li>한 단계에서 큐에 들어가는 원소가 2개 이상인 경우</li></ul></li></ul><h3>구현</h3><pre><code class="language-python">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()

</code></pre>입력<pre><code class="language-python">7 8
1 2
1 5
2 3
2 6
3 4
4 7
5 6
6 4
</code></pre><h2>문제 풀이</h2><h3>팀 결성</h3><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/b3921b24-4926-45e3-a223-459ae357ae7f/Untitled.png" alt="Untitled">풀이<pre><code class="language-python">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 &lt; 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')
</code></pre>입력<pre><code class="language-python">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
</code></pre><h3>도시 분할 계획</h3><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/ec5e3eab-479d-4868-a4ac-9fa4f81e71c6/Untitled.png" alt="Untitled"><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/7c940386-dd72-48eb-8000-b6e8b06b76ee/Untitled.png" alt="Untitled">풀이<pre><code class="language-python">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 &lt; 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개의 마을을 만듬
</code></pre>입력<pre><code class="language-python">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
</code></pre><h3>커리큘럼</h3><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/d02bdca4-92e8-4f36-a434-c36a9b76eb19/Untitled.png" alt="Untitled"><img src="https://s3-us-west-2.amazonaws.com/secure.notion-static.com/d9db954e-489d-421b-9cbd-5cb80ee62cf5/Untitled.png" alt="Untitled">풀이<pre><code class="language-python">
</code></pre>입력<pre><code class="language-python">5
10 -1
10 1 -1
4 1 -1
4 3 1 -1
3 3 -1
</code></pre><a href="https://www.acmicpc.net/problem/1922">1922번: 네트워크 연결</a><a href="https://www.acmicpc.net/problem/2252">2252번: 줄 세우기</a>

글 종류

이론 정리 알고리즘 이론에 대한 정리글입니다.

문제 풀이 알고리즘 문제 풀이입니다.

알고리즘 분류