나동빈님 유튜브의 '이것이 취업을 위한 코딩 테스트다'강의와 교재 내용을 공부하고, 그 내용을 정리한다.
(내용의 출처는 모두 동빈나, 그리고 책 '이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저'임을 사전에 밝힙니다.)
코딩 테스트에 자주 출제되는 그래프 관련 알고리즘에 대해 알아보자.
강의 영상은 다음과 같다.
https://www.youtube.com/watch?v=aOhhNFTIeFI&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=8
목차
1. 서로소 집합 알고리즘 (Disjoint Sets Algorithm)
1) 서로소 집합 (Disjoint Sets)
서로소 집합이란, 공통원소가 없는 두 집합을 말한다.
예를 들어, {1, 2}, {3, 4}는 서로 소로소 관계이고, {1, 2}와 {2, 3}은 {2}라는 공통의 원소가 존재하므로 서로소 관계가 아니다.
2) 서로소 집합 자료구조 (Disjoint Set Data Structure)
서로소 집합 자료구조란, 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조를 말한다.
이 자료구조는 다음과 같은 두 종류의 연산을 지원한다.
- 합집합(Union) : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다.
- 찾기(Find) : 특정 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다.
서로소 집합 자료구조는 이러한 특징에 따라 'Union Find Data Structure'로 불리기도 한다.
여러 Union 연산이 주어졌을 때, 서로소 집합 자료구조의 동작 과정은 다음과 같다.
- 합집합(Union)연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.
- A와 B의 root node A', B'을 각각 찾는다.
- A'을 B'의 부모 노드로 설정한다.
- 모든 합집합 연산을 처리할 때까지 1번의 과정을 반복한다.
(1) 서로소 집합 자료구조 동작 과정
동작 과정을 예시를 통해 알아보자.
처리할 연산은 \(Union(1, 4)\), \(Union(2, 3)\), \(Union(2, 4)\), \(Union(5, 6)\) 으로 가정하자.
\(Union\)함수의 각 인자는 노드의 번호이다.
[Step 0] 노드의 개수 크기의 부모 테이블을 초기화한다.
처음에는 부모를 자기 자신으로 설정한다. (서로 다른 6개의 집합)
[Step 1] \(Union (1, 4)\)
노드 1과 노드 4의 루트 노드를 각각 찾는다.
현재 루트 노드는 각각 1과 4이므로, 더 큰 번호에 해당하는 루트 노드 4의 부모를 1로 설정한다.
(일반적으로 큰 루트 노드가 작은 노드를 가리키도록 만든다.)
Table도 바뀌었음을 확인해볼 수 있다.
[Step 2] \(Union (2, 3)\)
노드 2와 노드 3의 루트 노드를 각각 찾는다. 이전과 같은 원리로 진행한다.
[Step 3] \(Union (2, 4)\)
노드 2와 노드 4의 루트 노드를 찾는다. 현재 루트 노드는 각각 2와 1이므로, 큰 번호에 해당하는 루트 노드 2의 부모를 1로 설정한다.
이때, 루트 노드를 기준으로 부모 노드를 갱신한다는 점에 유의하자.
그리고 주의할 점은, 테이블이 나타내는 것은 부모 노드라는 점이다.
3번 집합과 4번 집합은 같은 집합으로 연결되어 있다고 볼 수 있는데, 각각 해당하는 부모 노드는 다르다.
따라서 두 원소가 같은 집합에 포함되었는지 확인하기 위해서는 루트 노드를 확인해야 한다.
3번 노드의 루트 노드와 4번 노드의 루트 노드가 1로 같기 때문에 서로 같은 집합에 속해 있는 것으로 볼 수 있다.
[Step 4] \(Union (5, 6)\)
노드 5와 노드 6의 루트 노드를 찾는다. 현재 루트 노드는 각각 5와 6이므로 다음과 같이 연결할 수 있다.
결과를 보면, 서로소 집합 자료구조에서는 연결성을 통해 집합의 형태를 쉽게 확인해볼 수 있다.
아래와 같이 하나의 루트 노드에 트리 형태로 구성된 그래프를 하나의 집합으로 보는 것이다.
따라서 주어진 Union 함수를 실행하면 {1, 2, 3, 4}, {5, 6}과 같이 두 개의 집합이 생성되며, 서로 서로소 관계임을 쉽게 확인할 수 있다.
(2) 서로소 집합 자료구조의 문제점
기본적인 형태의 서로소 집합 자료구조에서는 루트 노드에 즉시 접근할 수 없다.
루트 노드를 찾기 위해서는 부모 테이블을 계속해서 확인하며 거슬러 올라가야 하기 때문이다.
위의 예시에서 노드 3번의 루트 노드를 찾기 위해서는 부모 노드를 두 번 거쳐야 한다.
이렇게 기본적인 방법의 자료구조는 수행시간 측면에서 문제점이 발생한다.
즉, 합집합 연산이 편향되게 이루어지는 경우, 찾기 함수가 비효율적으로 동작하게 된다.
찾기 함수는 매번 현재 노드에서 부모 테이블을 참조하여 그 부모가 자기 자신일 때까지 (루트 노드 : 부모 노드가 자기 자신) 재귀적으로 호출해서 확인해야 하는 과정을 반복해야 하기 때문이다.
최악의 경우 찾기 함수를 호출할 때 모든 노드를 다 확인하게 되어 시간 복잡도가 \(O(V)\)가 된다.
예를 들어, {1, 2, 3, 4, 5} 5개 원소가 존재할 때, 단순히
\(Union(4, 5)\), \(Union(3, 4)\), \(Union(2, 3)\), \(Union(1, 2)\)
와 같은 순서로 Union 함수를 실행한다고 하면, 아래와 같은 결과를 보일 것이다.
이때 5번 노드의 루트 노드를 찾기 위해 \(Find(5)\)를 호출하면, 모든 노드에 대해 \(Find\) 함수를 호출한다.
(3) 서로소 집합 자료구조: 경로 압축(Path Compression) 기법
따라서 Find 함수를 최적화하기 위해 고안한 방법이 바로 경로 압축이다.
경로 압축이란, 루트 노드까지 도달하기 위한 경로를 압축하여 시간을 단축한다는 의미를 갖는다.
구현 로직은 매우 간단한데, Find 함수를 재귀적으로 호출한 뒤에 부모 테이블 값을 바로 갱신해버리는 것이다.
# 특정 원소가 속한 집합 찾기
def find_parent(parent, x):
# 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if parent[x] != x:
parent[x] = find_parent(parent, parent[x]) # find 연산 실행 후에는 부모 테이블의 값이 루트가 됨
return parent[x]
경로 압축을 진행한 이후의 앞선 예시의 테이블과 그래프는 다음과 같이 변경된다.
기본적인 방법에 비해 시간 복잡도가 훨씬 효율적이다.
2) 경로 압축을 적용한 서로소 집합 자료구조 소스코드
(1) 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
# 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=' ')
(2) C++ 코드
#include <bits/stdc++.h>
using namespace std;
// 노드의 개수(V)와 간선(Union 연산)의 개수(E)
// 노드의 개수는 최대 100,000개라고 가정
int v, e;
int parent[100001]; // 부모 테이블 초기화
// 특정 원소가 속한 집합을 찾기
int findParent(int x) {
// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if (x == parent[x]) return x;
return parent[x] = findParent(parent[x]);
}
// 두 원소가 속한 집합을 합치기
void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
int main(void) {
cin >> v >> e;
// 부모 테이블상에서, 부모를 자기 자신으로 초기화
for (int i = 1; i <= v; i++) {
parent[i] = i;
}
// Union 연산을 각각 수행
for (int i = 0; i < e; i++) {
int a, b;
cin >> a >> b;
unionParent(a, b);
}
// 각 원소가 속한 집합 출력하기
cout << "각 원소가 속한 집합: ";
for (int i = 1; i <= v; i++) {
cout << findParent(i) << ' ';
}
cout << '\n';
// 부모 테이블 내용 출력하기
cout << "부모 테이블: ";
for (int i = 1; i <= v; i++) {
cout << parent[i] << ' ';
}
cout << '\n';
}
2. 서로소 집합을 활용한 사이클 판별
서로소 집합 자료구조는 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다.
(참고 - 방향 그래프에서의 사이클 여부는 DFS를 이용하여 판별할 수 있다.)
사이클 판별 알고리즘은 다음과 같다.
- 각 간선을 하나씩 확인하며 두 노드의 루트 노드를 확인한다.
- 루트 노드가 서로 다르다면 두 노드에 대해 합집합(Union) 연산을 수행한다.
- 루트 노드가 서로 같다면 사이클(Cycle)이 발생한 것이다.
- 그래프에 포함된 모든 간선에 대해 1번 과정을 반복한다.
1) 동작 과정
간단한 예시에 적용해보자.
위와 같은 그래프가 있을 때, edge (1, 2)와 (1, 3)의 각 노드에 Find 연산을 진행하여 루트 노드에 대해 Union 연산을 적용한다.
즉, 간선을 통해 연결된 두 노드를 같은 집합에 속하도록 만들어 주는 것이다.
이제 남은 edge (2, 3)에 같은 과정을 반복하는데, 이미 노드 2와 노드 3의 루트 노드는 모두 1이다.
즉, 간선 정보를 확인했을 때 이미 두 노드가 같은 집합에 속해있다.
이러한 상황일 때 사이클이 발생했다고 판별할 수 있다.
2) 서로소 집합을 활용한 사이클 판별 소스코드
(1) 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
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("사이클이 발생하지 않았습니다.")
(2) C++ 소스코드
#include <bits/stdc++.h>
using namespace std;
// 노드의 개수(V)와 간선(Union 연산)의 개수(E)
// 노드의 개수는 최대 100,000개라고 가정
int v, e;
int parent[100001]; // 부모 테이블 초기화
// 특정 원소가 속한 집합을 찾기
int findParent(int x) {
// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if (x == parent[x]) return x;
return parent[x] = findParent(parent[x]);
}
// 두 원소가 속한 집합을 합치기
void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
int main(void) {
cin >> v >> e;
// 부모 테이블상에서, 부모를 자기 자신으로 초기화
for (int i = 1; i <= v; i++) {
parent[i] = i;
}
bool cycle = false; // 사이클 발생 여부
for (int i = 0; i < e; i++) {
int a, b;
cin >> a >> b;
// 사이클이 발생한 경우 종료
if (findParent(a) == findParent(b)) {
cycle = true;
break;
}
// 사이클이 발생하지 않았다면 합집합(Union) 연산 수행
else {
unionParent(a, b);
}
}
if (cycle) {
cout << "사이클이 발생했습니다." << '\n';
}
else {
cout << "사이클이 발생하지 않았습니다." << '\n';
}
}
3. 최소 신장 트리 (Minimum Spanning Tree, MST)
최소 신장 트리 알고리즘을 알아보기 위해, 먼저 신장 트리의 개념을 살펴보자.
신장 트리란, 그래프에서 모든 노드를 포함하면서 사이클은 존재하지 않는 부분 그래프를 의미한다.
(모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 하다.)
아래 예시를 보자.
오른쪽 그래프는 {4, 6, 7} 부분에 사이클이 존재함을 확인할 수 있다.
신장 트리는 모든 노드가 연결은 되어 있지만, 일부 간선은 사용하지 않아도 괜찮도록 해준다는 점에서 실제 문제 상황에서 많이 사용된다.
최소 신장 트리는, 최소한의 비용으로 구성되는 신장 트리를 말한다.
예를 들어, 3개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우를 생각해보자.
이때 최소 신장 트리를 찾으면 최소한의 비용으로 모든 도시를 연결할 수 있다.
4. 크루스컬 알고리즘 (Kruskal Algorithm)
크루스컬 알고리즘은 대표적인 최소 신장 트리 알고리즘이다.
그리디 알고리즘으로 분류되며, 동작 과정은 다음과 같다.
- 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
- 간선을 하나씩 확인하며 현재 간선이 사이클을 발생시키는지 확인한다.
- 발생하지 않는 경우 최소 신장 트리에 포함시키고, 발생하는 경오 포함시키지 않는다.
- 모든 간선에 대해 2번의 과정을 반복한다.
1) 크루스컬 알고리즘 동작 과정
예시로 동작 과정을 살펴보자.
[Step 0] 그래프의 모든 간선 정보에 대해 오름차순 정렬을 수행한다.
참고로, 결과인 최소 신장 트리의 간선 개수는 (노드 개수 - 1)이다. 이는 트리의 특성이며, 사이클이 존재하지 않기 때문에 조금만 생각해보면 알 수 있을 것이다.
[Step 1] 처리하지 않은 간선 중 가장 짧은 간선인 (3, 4)를 선택하여 처리한다.
서로 같은 집합에 속할 수 있도록 \(Union(3, 4)\) 함수를 호출한다.
[Step 2, 3] (4, 7), (4, 6)에 대해 같은 과정을 반복한다.
[Step 4] 다음 간선 (6, 7)을 처리한다.
그런데 6번 노드와 7번 노드는 이미 같은 집합에 속해있기 때문에 이 간선을 포함시킨다면 사이클이 발생하게 된다.
따라서 (6, 7) 간선은 무시한다.
[Step 5, 6, 7, 8, 9] 같은 과정을 모든 간선에 대해 계속해서 반복한다.
모든 간선에 대해 반복하면 아래와 같은 최소 신장 트리를 얻게 된다.
최소 신장 트리에 포함된 간선의 비용을 모두 더하면, 그 값이 최종 비용에 해당한다.
2) 크루스컬 알고리즘 구현
(1) 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) # 부모 테이블 초기화하기
# 모든 간선을 담을 리스트와, 최종 비용을 담을 변수
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)
파이썬에서는 튜플을 이용하여 '(비용, 노드 a, 노드 b)'와 같이 간선을 표현해주면 정렬 함수를 사용할 때 자동으로 첫 번째 요소를 기준으로 하기 때문에 비용 순으로 정렬하기 편해진다.
(2) C++ 소스코드
#include <bits/stdc++.h>
using namespace std;
// 노드의 개수(V)와 간선(Union 연산)의 개수(E)
// 노드의 개수는 최대 100,000개라고 가정
int v, e;
int parent[100001]; // 부모 테이블 초기화
// 모든 간선을 담을 리스트와, 최종 비용을 담을 변수
vector<pair<int, pair<int, int> > > edges;
int result = 0;
// 특정 원소가 속한 집합을 찾기
int findParent(int x) {
// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if (x == parent[x]) return x;
return parent[x] = findParent(parent[x]);
}
// 두 원소가 속한 집합을 합치기
void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
int main(void) {
cin >> v >> e;
// 부모 테이블상에서, 부모를 자기 자신으로 초기화
for (int i = 1; i <= v; i++) {
parent[i] = i;
}
// 모든 간선에 대한 정보를 입력 받기
for (int i = 0; i < e; i++) {
int a, b, cost;
cin >> a >> b >> cost;
// 비용순으로 정렬하기 위해서 튜플의 첫 번째 원소를 비용으로 설정
edges.push_back({cost, {a, b}});
}
// 간선을 비용순으로 정렬
sort(edges.begin(), edges.end());
// 간선을 하나씩 확인하며
for (int i = 0; i < edges.size(); i++) {
int cost = edges[i].first;
int a = edges[i].second.first;
int b = edges[i].second.second;
// 사이클이 발생하지 않는 경우에만 집합에 포함
if (findParent(a) != findParent(b)) {
unionParent(a, b);
result += cost;
}
}
cout << result << '\n';
}
C++에서는 pair를 중첩해서 간선을 표현해준다.
3) 크루스컬 알고리즘 성능 분석
크루스컬 알고리즘에서 가장 많은 시간을 요구하는 부분은 간선 정렬이다.
표준 라이브러리를 사용하여 간선을 비용 순으로 정렬할 때, 간선 개수 \(E\)에 대해 시간복잡도 \(O(ElogE)\)를 갖는다.
5. 위상 정렬 (Topological Sort)
위상 정렬이란, 사이클이 없는 방향 그래프(Directed Acyclic Graph, DAG)의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미한다.
예를 들어, 아래와 같이 선수과목을 고려하여 학습 순서를 설정한다고 해보자.
이때, 세 과목을 모두 수강하기 위한 학습 순서는 '자료구조 → 알고리즘 → 고급 알고리즘'이다.
'자료구조 → 고급 알고리즘 → 알고리즘'과 같은 과정은 불가능하다.
참고로 그래프는 노드와 간선으로 구성되며, 노드로 들어오는 간선의 개수는 진입차수(Indegree), 노드에서 나가는 간선의 개수는 진출차수(Outdegree)이다.
위상 정렬을 구현하는 방법은 총 두가지이다.
- DFS를 이용한 구현
- 큐를 이용한 구현
그중에서 큐를 이용한 위상 정렬 알고리즘을 알아볼 것이다. (큐 - FIFO, 즉 처음 들어온 데이터 먼저 나감)
동작 과정은 다음과 같다.
- 진입차수가 0인 모든 노드를 큐에 넣는다.
- 큐가 빌 때까지 다음의 과정을 반복한다.
- 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
- 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
결론적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다.
1) 위상 정렬 동작 과정
위상 정렬을 수행할 그래프를 준비한다. 이때 그래프는 Directed Acyclic Graph여야 한다.
[Step 0] 진입차수가 0인 모든 노드를 큐에 넣는다.
예시에서는 이에 따라 노드 1이 큐에 삽입되었다.
[Step 1] 큐에서 노드 1을 꺼내고, 노드 1에서 나가는 간선을 제거한다.
새롭게 진입차수가 0이 된 노드들을 큐에 삽입한다.
[Step 2] 큐에서 노드 2를 꺼내고, 노드 2에서 나가는 간선을 제거한다. (순서는 상관 없지만, 작은 번호부터 꺼내기로 한다.)
새롭게 진입차수가 0이 된 노드를 큐에 삽입한다.
[Step 3, 4, 5, 6] 노드 5, 노드 3, 노드 6, 노드 4에 대해 반복한다.
[Step 7] 최종적으로 나가는 간선을 제거한다. 진입차수가 0이 된 노드가 없으므로 과정을 종료한다.
이때 큐에 삽입된 전체 노드 순서는 '1 → 2 → 5 → 3 → 6 → 4 → 7'이다.
이것이 곧 위상 정렬의 결과이며, 전체 방향성에 어긋나지 않도록 각 노드를 차례로 나열한 것과 동일하다.
2) 위상 정렬의 특징
위상 정렬은 다음과 같은 특징을 갖는다.
- 위상 정렬은 DAG(Directed Acyclic Graph, 순환하지 않는 방향 그래프)에 대해서만 수행 가능하다.
- 위상 정렬에서는 여러 답이 존재할 수 있다.
- 한 단계에서 큐에 새롭게 들어가는 원소가 동시에 2개 이상인 경우이면 순서에 따라 경우가 나뉜다.
- 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다.
- 사이클에 포함된 원소 중 어떤 것도 큐에 들어가지 못한다.
- 스택과 DFS를 이용하여 수행할 수도 있다.
3) 위상 정렬 구현
(1) 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():
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()
(2) C++ 소스코드
#include <bits/stdc++.h>
using namespace std;
// 노드의 개수(V)와 간선의 개수(E)
// 노드의 개수는 최대 100,000개라고 가정
int v, e;
// 모든 노드에 대한 진입차수는 0으로 초기화
int indegree[100001];
// 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
vector<int> graph[100001];
// 위상 정렬 함수
void topologySort() {
vector<int> result; // 알고리즘 수행 결과를 담을 리스트
queue<int> q; // 큐 라이브러리 사용
// 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
for (int i = 1; i <= v; i++) {
if (indegree[i] == 0) {
q.push(i);
}
}
// 큐가 빌 때까지 반복
while (!q.empty()) {
// 큐에서 원소 꺼내기
int now = q.front();
q.pop();
result.push_back(now);
// 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
for (int i = 0; i < graph[now].size(); i++) {
indegree[graph[now][i]] -= 1;
// 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
if (indegree[graph[now][i]] == 0) {
q.push(graph[now][i]);
}
}
}
// 위상 정렬을 수행한 결과 출력
for (int i = 0; i < result.size(); i++) {
cout << result[i] << ' ';
}
}
int main(void) {
cin >> v >> e;
// 방향 그래프의 모든 간선 정보를 입력 받기
for (int i = 0; i < e; i++) {
int a, b;
cin >> a >> b;
graph[a].push_back(b); // 정점 A에서 B로 이동 가능
// 진입 차수를 1 증가
indegree[b] += 1;
}
topologySort();
}
4) 위상 정렬 알고리즘 성능 분석
위상 정렬을 위해서는 차례대로 모든 노드를 확인하며 각 노드에서 나가는 간선을 차례대로 제거한다.
따라서 시간 복잡도는 \(O(V+E)\)이다.
최근댓글