🔎 신장 트리
신장 트리란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미함
모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 함 따라서 이러한 그래프를 신장 트리라고 부름
크루스칼 알고리즘
최소한의 비용으로 구성되는 신장 트리 = 최소 신장 트리
신장 트리 중 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘 = 최소 신장 트리 알고리즘
ex) 여러 N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우
크루스칼 알고리즘은 대표적인 최소 신장 트리 알고리즘이며 그리디 알고리즘으로 분류됨
크루스칼 알고리즘 동작 과정
- 간선 데이터를 비용에 따라 오름차순으로 정렬함
- 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인함
2-1. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킴
2-2. 사이클이 발생하는 경우 최소 신장 트리에 포함키지 않음 - 모든 간선에 대하여 2번의 과정을 반복함
쿠르스칼 알고리즘 동작 과정 예시
[초기 단계]: 그래프의 모든 간선 정보에 대하여 오름차순 정렬을 수행함
| 간선 | (3, 4) | (4, 7) | (4, 6) | (6, 7) | (1, 2) | (2, 6) | (2, 3) | (5, 6) | (1, 5) |
|---|---|---|---|---|---|---|---|---|---|
| 비용 | 7 | 13 | 23 | 25 | 29 | 34 | 35 | 53 | 75 |
Step 1: 가장 짧은 간선을 선택함, (3, 4)가 선택되므로 노드 3과 노드 4에 대하여 union 함수를 수행함 (노드 3과 노드 4를 동일한 집합에 속하도록 만듦)
| 간선 | (3, 4) | (4, 7) | (4, 6) | (6, 7) | (1, 2) | (2, 6) | (2, 3) | (5, 6) | (1, 5) |
|---|---|---|---|---|---|---|---|---|---|
| 비용 | 7 | 13 | 23 | 25 | 29 | 34 | 35 | 53 | 75 |
Step 2: 그다음 비용이 가장 작은 간선을 선택함, (4, 7)이 선택되고 현재 노드 4와 노드 7은 같은 집합에 속해있지 않으므로 노드 4과 노드 7에 대하여 union 함수를 수행함
| 간선 | (3, 4) | (4, 7) | (4, 6) | (6, 7) | (1, 2) | (2, 6) | (2, 3) | (5, 6) | (1, 5) |
|---|---|---|---|---|---|---|---|---|---|
| 비용 | 7 | 13 | 23 | 25 | 29 | 34 | 35 | 53 | 75 |
Step 3: 그다음 비용이 가장 작은 간선을 선택함, (4, 6)이 선택되고 현재 노드 4와 노드 6은 같은 집합에 속해있지 않으므로 노드 4과 노드 6에 대하여 union 함수를 수행함
| 간선 | (3, 4) | (4, 7) | (4, 6) | (6, 7) | (1, 2) | (2, 6) | (2, 3) | (5, 6) | (1, 5) |
|---|---|---|---|---|---|---|---|---|---|
| 비용 | 7 | 13 | 23 | 25 | 29 | 34 | 35 | 53 | 75 |
Step 4: 그다음 비용이 가장 작은 간선을 선택함, (6, 7)이 선택되고 현재 노드 6과 노드 7의 루트 노드가 이미 동일한 집합에 포함되어 있으므로 신장 트리에 포함하지 않아야 함
따라서 union 함수를 호출하지 않음
| 간선 | (3, 4) | (4, 7) | (4, 6) | (6, 7) | (1, 2) | (2, 6) | (2, 3) | (5, 6) | (1, 5) |
|---|---|---|---|---|---|---|---|---|---|
| 비용 | 7 | 13 | 23 | 25 | 29 | 34 | 35 | 53 | 75 |
Step 5: 그다음 비용이 가장 작은 간선을 선택함, (1, 2)가 선택되고 현재 노드 1과 노드 2는 같은 집합에 속해있지 않으므로 노드 1과 노드 2에 대하여 union 함수를 수행함
| 간선 | (3, 4) | (4, 7) | (4, 6) | (6, 7) | (1, 2) | (2, 6) | (2, 3) | (5, 6) | (1, 5) |
|---|---|---|---|---|---|---|---|---|---|
| 비용 | 7 | 13 | 23 | 25 | 29 | 34 | 35 | 53 | 75 |
Step 6 ~ 9: 위와 같은 방식으로
Step 6: (2, 6)은 union 함수를 수행
Step 7: (2, 3)은 union 함수를 수행하지 않음
Step 8: (5, 6)은 union 함수를 수행
Step 9: (1, 5)는 union 함수를 수행하지 않음
| 간선 | (3, 4) | (4, 7) | (4, 6) | (6, 7) | (1, 2) | (2, 6) | (2, 3) | (5, 6) | (1, 5) |
|---|---|---|---|---|---|---|---|---|---|
| 비용 | 7 | 13 | 23 | 25 | 29 | 34 | 35 | 53 | 75 |
결과
위의 과정을 통해 최소 신장 트리를 찾을 수 있음
최소 신장 트리에 포함되어 있는 간선의 비용만 모두 더하면, 그 값이 최종 비용에 해당함
(참고: 신장 트리에 포함되는 간선의 개수 = '노드의 개수 = 1')
간선의 개수가 E개일 때, O(ElogE)의 시간 복잡도를 가짐
크루스칼 알고리즘 소스코드
🔎 위상 정렬
위상 정렬이란 사이클이 없는 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'임
정렬 알고리즘의 일종, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘
진입차수(Indegree): 특정한 노드로 들어오는 간선의 개수
진출차수(Outdegree): 특정한 노드에서 나가는 간선의 개수
위상 정렬 알고리즘 동작 과정
- 진입차수가 0인 모든 노드를 큐에 넣음
- 큐가 빌 때까지 다음의 과정을 반복함
2-1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거함
2-2. 새롭게 진입차수가 0이 된 노드를 큐에 넣음
=> 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같음
큐가 빌 때까지 큐에서 원소를 계속 꺼내서 처리하는 과정을 반복함
모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단가능
위상 정렬 알고리즘 동작 과정 예시
사이클이 없는 방향 그래프 (DAG)
[초기 단계]: 진입차수가 0인 모든 노드를 큐에 넣음
노드 1의 진입차수만 0이기에 큐에 노드 1만 삽입함
| 노드 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 진입차수 | 0 | 1 | 1 | 2 | 1 | 2 | 1 |
| 큐 | 노드 1 |
|---|
Step 1: 큐에서 노드 1을 꺼내고, 노드 1과 연결되어 있는 간선들을 제거함
이후 새롭게 진입차수가 0이 된 노드들을 큐에 삽입함
=> 노드 2와 노드 5를 큐에 삽입함
| 노드 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 진입차수 | 0 | 0 | 1 | 2 | 0 | 2 | 1 |
| 큐 | 노드 2, 노드 5 |
|---|
Step 2: 큐에서 노드 2를 꺼낸 뒤 노드 2에서 나가는 간선을 제거함
이후 새롭게 진입차수가 0이 된 노드들을 큐에 삽입함
=> 노드 3을 큐에 삽입함
| 노드 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 진입차수 | 0 | 0 | 0 | 2 | 0 | 1 | 1 |
| 큐 | 노드 5, 노드 3 |
|---|
Step 3 ~ 6: 위와 같은 방식으로
Step 3: 노드 5를 꺼냄, 노드 6을 큐에 삽입함 (큐: 노드 3, 노드 6)
Step 4: 노드 3을 꺼냄, 새롭게 진입차수 0 되는 노드 없으므로 넘어감 (큐: 노드 6)
Step 5: 노드 6을 꺼냄, 노드 4를 큐에 삽입함 (큐: 노드 4)
Step 6: 노드 4를 꺼냄, 노드 7을 큐에 삽입함 (큐: 노드 7)
Step 7: 노드 7을 꺼냄, 새롭게 진입차수 0 되는 노드 없으므로 넘어감
큐가 비었기 때문에 끝!
위 과정을 수행하는 동안 큐에서 빠져나간 노드를 순서대로 출력하면, 그것이 바로 위상 정렬을 수행한 결과가 됨
위상 정렬 결과: 1 -> 2 -> 5 -> 3 -> 6 -> 4 -> 7
위상 정렬의 특징
위상 정렬은 DAG(Direct Acyclic Graph, 순환하지 않는 방향 그래프)에 대해서만 수행할 수 있음
위상 정렬에서는 여러 가지 답이 존재할 수 있음 (한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우)
모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있음
차례대로 모든 노드를 확인하며 각 노드에서 나가는 간선을 차례대로 제거해야 함
시간복잡도는 O(V + E)
✏️ 실전 문제
📝 도시 분할 계획
동물원에서 막 탈출한 원숭이 한 마리가 세상 구경을 하고 있음
어느 날 원숭이는 '평화로운 마을'에 잠시 머물렀는데 마침 마을 사람들은 도로 공사 문제로 회의 중이었음
마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있음
길은 어느 방향으로든지 다닐 수 있는 편리한 길이며, 길마다 길을 유지하는데 드는 유지비가 있음
마을의 이장은 마을을 2개의 분리된 마을로 분할할 계획을 세우고 있음
마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 함
각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻
마을에는 집이 하나 이상 있어야 함
마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 됨
일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있음
그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 있는 길들을 필요가 없으므로 없앨 수 있음
마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶음
이것을 구하는 프로그램을 작성하시오
- 입력 조건
- 첫째 줄에 집의 개수 N, 길의 개수 M이 주어짐, N은 2 이상 100,000 이하인 정수, M은 1 이상 1,000,000 이하인 정수
- 그다음 줄부터 M줄에 걸쳐 길의 정보가 A, B, C 3개의 정수로 공백으로 구분되어 주어짐, A번 집과 B번 집을 연결하는 길의 유지비가 C(1 ≤ C ≤ 1,000)라는 뜻 - 출력 조건
- 첫째 줄에 길을 없애고 남은 유지비 합의 최솟값을 출력함
문제 해설
이 문제의 핵심 아이디어는 전체 그래프에서 2개의 최소 신장 트리를 만들어야 한다는 것
크루스칼 알고리즘으로 최소 신장 트리를 찾은 뒤에 최소 신장 트리를 구성하는 간선 중에서 가장 비용이 큰 간선을 제거하는 것
소스코드
📝 커리큘럼
수빈이는 온라인으로 컴퓨터공학 강의를 듣고 있음
이때 각 온라인 강의는 선수 강의가 있을 수 있는데, 선수 강의가 있는 강의는 선수 강의를 먼저 들어야만 해당 강의를 들을 수 있음
ex) '알고리즘' 강의의 선수 강의 => '자료구조'와 '컴퓨터 기초'
=> '자료구조'와 '컴퓨터 기초'를 모두 들은 이후에 '알고리즘' 강의를 들을 수 있음
수빈이는 총 N개의 강의를 듣고자 함
모든 강의는 1번부터 N번까지의 번호를 가짐
또한 동시에 여러 개의 강의를 들을 수 있다고 가정함
ex) 1번과 2번의 강의는 선수 강의 없음, 3번 강의의 선수 강의는 1번과 2번 강의
1번 강의: 30시간, 2번 강의: 20시간, 3번 강의: 40시간
=> 3번 강의를 수강하기까지의 최소 시간은 70시간
수빈이가 듣고자 하는 N개의 강의 정보가 주어졌을 때, N개의 강의에 대하여 수강하기까지 걸리는 최소 시간을 각각 출력하는 프로그램을 작성하시오
- 입력 조건
- 첫째 줄에 수빈이가 듣고자 하는 강의의 수 N (1 ≤ N ≤ 500)이 주어짐
- 다음 N개의 줄에는 각 강의의 강의 시간과 그 강의를 듣기 위해 먼저 들어야 하는 강의들의 번호가 자연수로 주어지며, 각 자연수는 공백으로 구분함
이때 강의 시간은 100,000 이하의 자연수
- 각 강의 번호는 1부터 N까지로 구성되며, 각 줄은 -1로 끝남 - 출력 조건
- N개의 강의에 대하여 수강하기까지 걸리는 최소 시간을 한 줄에 하나씩 출력함
문제 해설
이 문제는 위상 정렬 알고리즘의 응용 문제임
각 노드(강의)에 대하여 인접한 노드를 확인할 때, 인접한 노드에 대하여 현재보다 강의 시간이 더 긴 경우를 찾는다면, 더 오랜 시간이 걸리는 경우의 시간 값을 저장하는 방식으로 결과 테이블을 갱신하여 답을 구할 수 있음
참고) 리스트의 값을 복제해야 할 때는 deepcopy() 함수를 사용
소스코드
📒 이것이 코딩 테스트다 교재를 통해 학습한 내용을 정리하였습니다.
