DFS && BFS
예제를 바탕으로 이해하자
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
예제 입력
5 5 3
5 4
5 2
1 2
3 4
3 1
예제 출력
3 1 2 5 4
3 1 4 2 5
간선을 정리하면 다음과 같이 나온다
1
2
3
4
5
1 -> [2, 3]
2 -> [1, 5]
3 -> [1, 4]
4 -> [3, 5]
5 -> [2, 4]
이어서 그래프를 그리면 다음과 같다
3이 색칠된 이유는 V가 3이니, 3에서 시작하기 때문이다
그리고 문제를 보면 정점이 여러 개인 경우 정점 번호가 작은 것 부터 방문을 하니, 미리 전체 그래프에 오름차순을 적용하자
DFS의 경우는 stack에 추가할 때 pop()을 위해 내림차순하면 되겠다.
우선 DFS의 경우에는 Stack을 사용하는데 Stack에 중복된 노드를 추가하느냐 안하느냐에 따라 답이 달라질 수 있기에 잘 선택하길 바란다.
이번 문제에서는 Stack에 중복된 노드를 추가를 허용한다.
(단 출력된 노드는 넣지 않는다.)
그렇게 되면 아래와 같다
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
초기경로 : X
stack = [3]
경로 : 3
stack = [4, 1]
경로 : 3 -> 1
stack = [4, 2]
경로 : 3 -> 1 -> 2
stack = [4, 5]
경로 : 3 -> 1 -> 2 -> 5
stack = [4, 4]
경로 : 3 -> 1 -> 2 -> 5 -> 4
stack = [4]
경로 : 3 -> 1 -> 2 -> 5 -> 4
stack = []
위 흐름을 볼 때 DFS (stack) 에서는 노드를 경로로 출력하지 않았다면,
stack에 중복추가가 되는 것을 볼 수 있다.
다음은 BFS다
BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
초기경로 : X
queue = [3]
경로 : 3
queue = [1, 4]
경로 : 3 -> 1
queue = [4, 2]
경로 : 3 -> 1 -> 4
queue = [2, 5]
경로 : 3 -> 1 -> 4 -> 2
queue = [5]
경로 : 3 -> 1 -> 4 -> 2 -> 5
queue = []
BFS (queue)의 흐름을 보면 queue에는 중복노드 추가를 허용하지 않는 것을 알 수 있다.
전체 코드는 다음과 같다
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
// graph
import java.util.ArrayList;
// asc
import java.util.Collections;
// DFS
import java.util.Stack;
import java.util.List;
// BFS
import java.util.Queue;
import java.util.LinkedList;
// sys
import java.util.Arrays;
public class Main {
static ArrayList<Integer>[] graph;
static boolean[] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] NMV = br.readLine().split(" ");
int N = Integer.parseInt(NMV[0]);
int M = Integer.parseInt(NMV[1]);
int V = Integer.parseInt(NMV[2]);
// allocating size of graph;
graph = new ArrayList[N+1];
for (int i = 1; i < N+1; i++) {
graph[i] = new ArrayList<>();
}
// System.out.println(Arrays.toString(graph));
for (int i = 0; i < M; i++) {
String[] ab = br.readLine().split(" ");
int a = Integer.parseInt(ab[0]);
int b = Integer.parseInt(ab[1]);
graph[a].add(b);
graph[b].add(a);
}
// asc
for (int i = 1; i < N+1; i++) {
Collections.sort(graph[i]);
}
// test
// for (int i = 1; i < N+1; i++) {
// System.out.println(i + " -> " + graph[i]);
// }
// answer
visited = new boolean[N+1];
DFS(V);
System.out.println();
visited = new boolean[N+1];
BFS(V);
}
public static void DFS(int start) {
Stack<Integer> stack = new Stack<>();
stack.push(start);
while (!stack.isEmpty()) {
int node = stack.pop();
if (visited[node]) continue;
else visited[node] = true;
System.out.print(node + " ");
// neighbors
List<Integer> neighbors = graph[node];
for (int i = graph[node].size()-1; i >= 0; i--) {
int next = neighbors.get(i);
if (!visited[next]) {
stack.push(next);
}
}
}
}
public static void BFS(int start) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
visited[start] = true;
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");
for (int next : graph[node]) {
if (!visited[next]) {
visited[next] = true;
queue.offer(next);
}
}
}
}
}
