1. 그래프(Graph)
Graph
•
Computer Science의 대표적인 자료구조 중 하나입니다.
•
정점(Node, vertex)과 간선(Edge)로 이루어진 자료구조입니다.
•
차수(Degree) : 각 정점에 연결되어 있는 간선의 개수를 말합니다.
•
사이클(Cycle) : 자기 자신으로 다시 돌아올 수 있는 경로를 말합니다,
•
현실 세계의 많은 것들을 그래프로 나타낼 수 있기 때문에 그래프와 관련된 문제가 매우 많습니다.
2. 그래프에 관한 중요한 수학적 지식
Tip
•
간선의 개수는 대략적으로 정점의 제곱보다 작거나 같습니다.(정확히는 nC2 보다 작거나 같음)
•
즉, 간선의 최대 개수 = 정점의 개수 x (정점의 개수 - 1) / 2 혹은 간선의 개수는 정점의 개수 x (정점의 개수 - 1) / 2 보다 작거나 같습니다.
•
차수의 합 = 간선의 개수 x 2
3. 그래프의 구현 1 : 인접 행렬
그래프의 구현 1 : 인접 행렬
•
정점의 연결 관계를 2차원 배열에 0, 1로 표현할 수 있습니다.
•
그래프에서 할 수 있는 질문은 x, y가 연결돼 있는가?, x와 연결된 정점이 모두 무엇인가? 정도로 말할 수 있스습니다.
•
인접 행렬로 그래프를 구현했을 때 장점 : 두 정점 연결 여부를 O(1)에 알 수 있습니다.
•
인접 행렬로 그래프를 구현했을 때 단점 : 인접한 정점을 모두 찾는데 O(n)이 걸리며, n^2의 공간이 필요하게 됩니다.
func solution() -> Void {
guard let input: [String] = readLine()?.components(separatedBy: " ") else { return }
let n: Int = input.map { Int($0) }[0] ?? 0
let m: Int = input.map { Int($0) }[1] ?? 0
var myGraph: [[Int]] = Array(repeating: Array(repeating:0, count: n + 10), count: n + 10)
for _ in 0..<m {
guard let inputData: [String] = readLine()?.components(separatedBy: " ") else { return }
let a: Int = inputData.map { Int($0) }[0] ?? 0
let b: Int = inputData.map { Int($0) }[1] ?? 0
myGraph[a][b] = 1
myGraph[b][a] = 1
}
}
Swift
복사
4. 그래프의 구현 2 : 인접 리스트
그래프의 구현 2 : 인접 리스트
•
각각의 정점에 대하여 인접한 정점 번호를 저장합니다.
•
장점 : 인접한 정점을 모두 찾는 것이 O(degree)로 인접 행렬보다 빠르며, 필요한 만큼만 공간을 활용합니다.
•
단점 : x와 y 두 정점 연결 여부를 찾는 것이 O(degree)로 인접 행렬의 O(1)에 비해 느립니다.
func solution() -> Void {
guard let input: [String] = readLine()?.components(separatedBy: " ") else { return }
let n: Int = input.map { Int($0) }[0] ?? 0
let m: Int = input.map { Int($0) }[1] ?? 0
var myGraph: [Graph] = Array(repeating: Graph(), count: n + 10)
for _ in 0..<m {
guard let inputData: [String] = readLine()?.components(separatedBy: " ") else { return }
let a: Int = inputData.map { Int($0) }[0] ?? 0
let b: Int = inputData.map { Int($0) }[1] ?? 0
myGraph[a].edges.append(b)
myGraph[b].edges.append(a)
}
}
Swift
복사
5. 그래프 탐색(Graph Traversal)
Graph Traversal
•
그래프 탐색의 목적 : 그래프라는 자료구조에 어떠한 값이 저장되어 있는가?
•
위 질문을 알기 위해서 그래프를 순회해야 하는데, 대표적인 알고리즘으로, 깊이우선탐색, 너비우선탐색이 있습니다.
•
트리의 Pre-Order, In-Order, Post-Order 각각의 트리를 순회한다는 목적이 같고 방법만 다른 것과 마찬가지로, 깊이우선탐색과 너비우선탐색의 목적은 그래프 탐색으로 같지만 그 방법이 다름
</pre>
6. 깊이우선탐색(Depth First Search, DFS)
DFS
•
Stack을 이용하여 그래프를 순회하는 방법입니다.
•
나를 먼저 방문하고, 그 다음으로 인접한 노드를 차례로 방문합니다. (단, 방문했던 노드는 방문하지 않음)
•
Stack을 이용하기 때문에 재귀함수로 구현할 수 있습니다.
•
DFS는 모든 정점을 방문하고, 하나의 정점을 두번 이상 방문하지 않기 때문에 정확하다고 말할 수 있습니다.
•
O(노드의 개수 + 차수의 합) = O(노드의 개수 + 간선의 개수 x 2) = O(노드의 개수 + 간선의 개수) = O(V + E)의 시간복잡도를 가지게 됩니다.
func dfs(_ x: Int) -> Void {
visited[x] = true
print("\\(x) ", terminator: "")
for i in stride(from: 0, to: graph[x].edges.count, by: 1) {
let y: Int = graph[x].edges[i]
if !visited[y] {
dfs(y)
}
}
}
Swift
복사
7. 너비우선탐색(Breadth First Search, BFS)
BFS
•
Queue를 이용하여 그래프를 순회하는 방법입니다.
•
깊이우선탐색과 그래프 탐색이라는 목적은 같고 방법이 다르기 때문에, 탐색하는 순서가 다릅니다.
•
인접한 노드들을 우선 모두 색칠해 두고, 뻗어 나가는 철학을 가지고 있습니다.
•
시작점을 색칠하고 큐에 넣고, 큐에서 현재 위치를 빼고 인접한 노드들을 색칠하고 큐에 넣고 위와 같은 과정을 큐가 빌 때 까지 계속해서 반복하게 됩니다.
•
깊이우선과 마찬가지로 O(V + E)의 시간복잡도를 가집니다.
func bfs(_ start: Int) -> Void {
var queue: [Int] = []
queue.append(start)
visited[start] = true
while !queue.isEmpty {
let current: Int = queue.removeFirst()
print("\\(current) ", terminator: "")
for i in stride(from: 0, to: graph[current].edges.count, by: 1) {
let next: Int = graph[current].edges[i]
if !visited[next] {
visited[next] = true
queue.append(next)
}
}
}
}
Swift
복사