출처: 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략, 구종만 지음, 인사이트
DFS 스패닝 트리
- 어떤 그래프를 DFS했을 때, 탐색이 따라가는 간선들만을 모아 보았을 때의 트리.
DFS 스패닝 트리의 모든 간선을 네가지 중 하나로 분류할 수 있습니다.
1. 트리 간선
스패닝 트리에 포함된 간선.
2. 순방향 간선
스패닝 트리의 선조에서 자손으로 연결되지만 트리 간선이 아닌 간선.
ex. 그림의 (0, 6) 간선
3. 역방향 간선
스패닝 트리의 자손에서 선조로 연결되는 간선
ex. 그림의 (2, 0) 간선
4. 교차 간선
트리에서 선조와 자손 관계가 아닌 정점들 간에 연결된 간선
ex. 그림의 (6, 3) 간선
+) 무향 그래프
무향 그래프의 모든 간선은 양방향으로 통행 가능하므로 교차 간선이 있을 수 없습니다.
간선 (u, v)가 교차 간선이기 위해서는 v가 먼저 방문된 후 u를 방문하지 않고 종료해야 하는데, 무향 그래프의 경우 (u, v)를 이용해 v에서 u로 갈 수 있기 때문입니다. 또한 무향 그래프에서는 순방향 간선과 역방향 간선의 구분이 없습니다.
간선을 구분하는 방법
0. 탐색 과정에서 각 정점의 방문 여부와 몇번째 순서로 발견되었는지 기록해야 합니다.
dfs(u)내에서 간선 (u, v)를 검사했을 때
1. v가 방문된 적이 없다면
트리 간선
2. v가 방문된 적이 있다면
2-1. v가 u보다 더 늦게 발견됐다면
v는 u의 자손이기 때문에 순방향 간선
2-2. v가 u보다 일찍 발견됐다면
2-2-1. dfs(v)가 아직 종료되지 않았다면
v는 u의 선조이기 때문에 역방향 간선
2-2-2. dfs(v)가 이미 종료되었다면
교차 간선
간선을 분류하는 dfs 코드.
import Foundation
let v = 10
var adj = Array(repeating: [Int](), count: v + 1) // 인접 리스트
var discovered = Array(repeating: -1, count: v + 1) // i번 정점의 발견 순서
var finished = Array(repeating: false, count: v + 1)
var counter = 0
func dfs2(here: Int) {
discovered[here] = counter
counter += 1
for i in 0..<adj[here].count {
let there = adj[here][i]
if discovered[there] == -1 {
// tree edge
dfs2(here: there)
} else if discovered[here] < discovered[there] {
// there가 here보다 늦게 발견됐으면 there는 here의 후손
// forward edge
} else if finished[there] == false {
// dfs2(there)가 아직 종료하지 않았으면 there는 here의 선조
// back edge
} else {
// cross edge
}
}
finished[here] = true
}
절단점 찾기 알고리즘
무향 그래프의 절단점
- 이 점과 인접한 간선들을 모두 지웠을 때 해당 컴포넌트가 두 개 이상으로 나뉘어지는 정점.
ex. 그림에서의 1번, 3번, 5번 정점
어떤 정점이 절단점인지 확인하는 간단한 방법
해당 정점을 그래프에서 삭제한 뒤, 컴포넌트의 개수를 DFS로 센 후 개수가 이전보다 늘어났는지 확인하는 것.
DFS를 |V|번 수행.
한 번의 DFS로 그래프의 모든 절단점을 찾아내는 방법
0. 임의의 정점에서부터 DFS를 수행해 DFS 스패닝 트리를 만듭니다.
무향 그래프의 스패닝 트리에는 교차 간선이 없으므로 u와 연결된 정점들은 모두 u의 선조 혹은 자손입니다.
이때 u의 자손들을 루트로 하는 서브트리들은 서로 연결되어있지 않습니다. 이들을 연결하는 간선이 있다면 교차 간선일텐데, 무향 그래프에는 교차 간선이 있을 수 없기 때문입니다.
1. u가 지워졌을 때 그래프가 쪼개지지 않는 유일한 경우
그림처럼 u의 선조와 자손들이 전부 역방향 간선으로 연결되어있을 때 뿐입니다.
이것을 확인하는 방법은 DFS 함수가 각 정점을 루트로 하는 서브트리에서 역방향 간선을 통해 갈 수 있는 정점의 최소 깊이를 반환하도록 하는 것입니다. 만약 u의 자손들이 모두 역방향 간선을 통해 u의 선조로 올라갈 수 있다면 u는 절단점이 아닙니다.
2. u가 스패닝 트리의 루트라서 선조가 없는 경우
자손이 하나도 없거나 하나밖에 없을 때 -> 그래프가 쪼개지지 않음.
자손이 둘 이상의 자손을 가질 때 -> 절단점이 됨.
이 알고리즘을 구현할 때는 각 정점의 깊이를 비교하는 대신 각 정점의 발견 순서를 비교하는 형태로 코드를 작성해 구현을 간단하게 할 수 있습니다. 왜냐하면 우리가 알고 싶은 것은 결국 해당 서브트리가 u의 조상 중 하나와 연결되어 있는지인데, u의 조상들은 항상 u보다 먼저 발견되었겠죠. 따라서 해당 정점을 루트로 하는 서브트리에서 역방향 간선을 통해 닿는 정점들의 최소 발견 순서를 반환하도록 하면 됩니다.
무향 그래프에서는 교차 간선이 없기 때문에 finished 배열이 없어도 discovered 배열로 모든 간선을 구분할 수 있습니다.
import Foundation
let v = 10
var adj = Array(repeating: [Int](), count: v + 1) // 인접 리스트
var discovered = Array(repeating: -1, count: v + 1) // i번 정점의 발견 순서
var isCutVertex = Array(repeating: false, count: v + 1)
var counter = 0
func fincCutVertex(here: Int, isRoot: Bool) -> Int {
discovered[here] = counter
counter += 1
var result = discovered[here]
// 루트인 경우 절단점 판정을 위해 자손 서브트리의 개수를 센다.
var children = 0
for i in 0..<adj[here].count {
let there = adj[here][i]
if discovered[there] == -1 {
children += 1
// 서브트리에서 갈 수 있는 가장 높은 정점의 번호
let subtree = fincCutVertex(here: there, isRoot: false)
// 그 노드가 자기 자신 이하에 있다면 현재 위치는 절단점이다.
if !isRoot && subtree >= discovered[here] {
isCutVertex[here] = true
}
result = min(result, subtree)
} else {
result = min(result, discovered[there])
}
}
if isRoot {
isCutVertex[here] = children >= 2
}
return result
}
이중 결합 컴포넌트
- 무향그래프에서 절단점을 포함하지 않는 서브그래프
임의의 한 정점을 그래프에서 지우더라도 정점 간의 연결 관계가 유지됩니다.
강결합 컴포넌트(SCC)
이중 결합 컴포넌트와 비슷하지만 방향 그래프에서 정의되는 개념입니다.
방향 그래프 상에서 두 정점 u와 v에 대해 양 방향으로 가는 경로가 모두 있을 때 두 정점은 같은 SCC에 속해 있다고 말합니다.
각 SCC 사이를 연결하는 간선들을 모으면 SCC들을 정점으로 하는 DAG(방향성 비사이클 그래프)를 만들 수 있습니다.
그래프의 압축
- 원 그래프의 정점들을 SCC별로 분리하고 각 SCC를 표현하는 정점들을 갖는 새로운 그래프를 만드는 과정
강결합 컴포넌트(SCC) 분리 알고리즘
1. 간단한 방법
- 모든 정점에서 한 번씩 DFS
그러면 모든 정점 쌍에 대해 양방향 경로가 모두 있는지 쉽게 확인할 수 있지만 O(|V| * |E|) 시간이 소요됩니다.
2. 타잔의 알고리즘
- 한 번의 DFS로 각 정점을 SCC별로 분리
위 그림은 그래프의 가장 왼쪽 정점에서 DFS를 해서 얻을 수 있는 스패닝 트리입니다.
이 스패닝 트리를 적절히 자르기만 해도 정점들을 SCC로 분리할 수 있습니다.
타잔의 알고리즘은 DFS를 수행하면서 각 정점을 SCC로 묶습니다.
이를 위해 간선을 따라 재귀 호출이 반환될 때마다 이 간선을 자를지 여부를 결정합니다. 탐을 수행하면서 각 서브트리에 대한 정보를 수집한 후에야 간선을 자를지 말지 결정할 수 있기 때문입니다.
어떤 정점 v를 루트로 하는 서브트리를 탐색한 뒤, 그 부모인 u로 재귀호출을 반환하면서
1. 트리 간선 (u, v)를 자를 수 있는 경우
v에서 u로 갈 수 있는 경로가 없어야 합니다.
v를 루트로 하는 서브트리에서 u 혹은 그보다 높이 있는 정점에 닿을 수 있는 역방향 간선이 없어야 합니다.
2. 트리 간선 (u, v)를 자를 수 없는 경우
2-1. v를 루트로 하는 서브트리에서 v보다 먼저 발견된 정점으로 가는 역방향 간선이 있을 경우
2-1-1. 그런 역방향 간선이 없을 때, v보다 먼저 발견되었으면서 아직 SCC로 묶여 있지 않은 정점으로 가는 교차 간선이 있을 경우
스택에서 정점을 꺼내는 반복문은 분할 상환 분석을 이용해 총 수행 회수가 O(|V|)입니다.
따라서 이 알고리즘의 시간 복잡도 또한 O(|V| + |E|)가 됩니다.
import Foundation
let v = 10
var adj = Array(repeating: [Int](), count: v + 1) // 인접 리스트
var sccId = Array(repeating: -1, count: v + 1)
var discovered = Array(repeating: -1, count: v + 1) // i번 정점의 발견 순서
var stack = [Int]() // 정점의 번호를 담는 스택
var sccCounter = 0
var vertexCounter = 0
func scc(here: Int) -> Int {
discovered[here] = vertexCounter
vertexCounter += 1
var result = discovered[here]
stack.append(here)
for i in 0..<adj[here].count {
let there = adj[here][i]
if discovered[there] == -1 { // 트리 간선
result = min(result, scc(here: there))
} else if (sccId[there] == -1) {
// 아직 scc로 묶여 있지 않은 정점으로 가는 교차 간선
result = min(result, discovered[there])
}
}
// here에서 부모로 올라가는 간선을 끊어야 할 때
if result == discovered[here] {
// here를 루트로 하는 서브트리에 남아있는 정점들을 전부 하나의 컴포넌트로 묶는다.
while true {
let t = stack.removeLast()
sccId[t] = sccCounter
if t == here { break}
}
sccCounter += 1
}
return result
}
func tarjanSCC() -> [Int] {
for i in 1..<v + 1 {
if discovered[i] == -1 {
scc(here: i)
}
}
return sccId
}'알고리즘' 카테고리의 다른 글
| [Swift] 프로그래머스 - 카카오 표 편집 (0) | 2022.07.18 |
|---|---|
| [Swift] 백준 16113번 시그널 (0) | 2022.07.10 |
| [Swift] 프로그래머스 - 카카오 기둥과 보 설치 (0) | 2022.06.27 |
| [Swift] 프로그래머스 - 카카오 괄호 변환 (0) | 2022.06.27 |
| [Swift] 백준 1992번 쿼드트리 (0) | 2022.05.11 |
댓글