2. 문제 요약: 정점의 개수 N(1<= N <= 1000), 간선의 개수M(1<= M <= 10_000), 탐색을 시작할 정점의 번호 V가 있고, 임의의 그래프가 주어졌을 때, V를 시작으로 DFS 순서와 BFS 순서를 출력하는 문제이다.
3. 문제 접근 방법: DFS는 재귀로, BFS는 큐를 이용하여 구한다. 새로운 맛을 느끼기 위해 C 말고 다른 언어로 만들어 본다.
4. 주의할 점: BFS와 DFS는 경우에 따라 출력 순서가 달라질 수 있는데, 문제에서는 오름차순으로 출력하라고 했으니 주의해야 한다.
5. 문제에 얽힌 슬픈 이야기: 간선의 개수가 1만 개나 되기 때문에, 2차원 배열로 그래프를 표현하여 풀면 시간초과가 날 것이라는 헛된 예측을 했다.
막상 문제를 풀고, Swift로 이 문제를 푼 다른 사람들의 코드를 보니 다들 2차원 배열로 풀었다. 나만 Vertex 클래스나 Edge 클래스 만들고, Vertex에 Edge 리스트 붙여서 풀었다.
6. Swift(4.2) 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
import Foundation
class Vertex{
let value:Int
var links:[Edge]
init(_ value:Int) {
self.value = value
links = [Edge]()
}
func addVertex(vertex:Vertex, weight:Int)
{
let temp = Edge(to: vertex, weight: weight)
links.append(temp)
links.sort(by: {$0.toVertex.value < $1.toVertex.value})
}
}
class Edge{
let toVertex:Vertex
let weight:Int
init(to vertex:Vertex, weight:Int) {
toVertex = vertex
self.weight = weight
}
}
func dfs(root:Vertex, visited: inout [Bool])
{
print(root.value, terminator: " ")
visited[root.value] = true
for v in root.links
{
if !visited[v.toVertex.value]
{
dfs(root: v.toVertex, visited: &visited)
}
}
}
func bfs(root:Vertex, visited: inout [Bool], queue: inout [Vertex])
{
// print(root.value, terminator: "")
// visited[root.value] = true
queue.append(root)
visited[root.value] = true
while(!queue.isEmpty)
{
let newRoot = queue.removeFirst()
print(newRoot.value, terminator: " ")
for v in newRoot.links
{
if !visited[v.toVertex.value]
{
queue.append(v.toVertex)
visited[v.toVertex.value] = true
}
}
}
}
let input = readLine()!.split(separator: " ").map({Int($0)!})
let N = input[0]
let M = input[1]
let V = input[2]
var graph = [Vertex](repeating: Vertex(0), count: N + 1)
var visited = [Bool](repeating: false, count: N + 1)
var queue = [Vertex]()
for _ in 0..<M
{
let info = readLine()!.split(separator: " ").map({Int($0)!})
if graph[info[0]].value == 0
{
graph[info[0]] = Vertex(info[0])
}
if graph[info[1]].value == 0
{
graph[info[1]] = Vertex(info[1])
}
graph[info[0]].addVertex(vertex: graph[info[1]], weight: 0)
graph[info[1]].addVertex(vertex: graph[info[0]], weight: 0)
}
dfs(root: graph[V], visited: &visited)
visited = [Bool](repeating: false, count: N + 1)
print("")
bfs(root: graph[V], visited: &visited, queue: &queue)
print("")
| cs |
