DFS와 BFS - 1260
백준 실버 2
◼︎ DFS와 BFS
문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
예제 입력 1
1
2
3
4
5
6
4 5 1
1 2
1 3
1 4
2 4
3 4
예제 출력 1
1
2
1 2 4 3
1 2 3 4
예제 입력 2
1
2
3
4
5
6
5 5 3
5 4
5 2
1 2
3 4
3 1
예제 출력 2
1
2
3 1 2 5 4
3 1 4 2 5
예제 입력 3
1
2
1000 1 1000
999 1000
예제 출력 3
1
2
1000 999
1000 999
► Code
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
public class Main {
static int[][] arr;
static boolean[] visit;
static void dfs(int Node) {
//방문 기록
visit[Node] = true;
// 방문한 노드 출력
System.out.print(Node + " ");
//스택 자료구조 할당
Stack<Integer> stk = new Stack<>();
stk.push(Node);
//스택 빌 때까지 반복
while (!stk.isEmpty()) {
int nowNode = stk.pop();
for (int i = 0; i < arr.length; i++) {
if (visit[i]) {
continue;
}
if (arr[nowNode][i] == 1 && !visit[i]) {
dfs(i);
}
}
}
//dfs 재귀호출
}
static void bfs(int Node) {
visit[Node] = true;
//큐로 구현
Queue<Integer> que = new LinkedList<>();
//시작 노드 큐 삽입
que.add(Node);
//큐가 빌 때까지 현재 노드 poll 하고 방문
while (!que.isEmpty()) {
//일단 큐에서 시작노드 poll 하고, 시작노드와 인접한 노드 삽입
int nowNode = que.poll();
System.out.print(nowNode + " ");
for (int i = 0; i < arr.length; i++) {
//인접 행렬 1이고, 방문 안 했다면 큐 삽입
if (arr[nowNode][i] == 1 && !visit[i]) {
que.add(i);
// 인접 노드 방문 체크
visit[i] = true;
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
//정점개수 n, 간선 개수 m, 시작 정점 번호 v 입력받기
String[] info = br.readLine().split(" ");
int n = Integer.parseInt(info[0]);
int m = Integer.parseInt(info[1]);
int vtx = Integer.parseInt(info[2]);
//인접행렬 할당
arr = new int[n + 1][n + 1];
visit = new boolean[n + 1];
//간선 연결 하기 간선개수만큼 반복
for (int i = 0; i < m; i++) {
String[] ab = br.readLine().split(" ");
int from = Integer.parseInt(ab[0]);
int to = Integer.parseInt(ab[1]);
arr[from][to] = 1;
arr[to][from] = 1;
}
//시작노드
//dfs 수행
dfs(vtx);
visit = new boolean[n + 1];
System.out.println();
//bfs 수행
bfs(vtx);
//결과 출력하기
}
}
► 시간 소요한 것
DFS 스택 무한루프
스택에서 pop이 아니라 peek을 해서 무한루프에 빠졌다.
그 이유
스택에서 원소를 제거하지 않으면 기존에 방문한 노드를 계속 참조하기 때문에 무한루프에 빠졌었다.
peek과 pop의 차이를 알고 있었음에도 불구, 최상단 노드를 사용하는 건 비슷하니까 그냥 해볼까 했던게 화근이었다. (;) → pop으로 스택의 최상단 노드를 빼내야, 인접한 노드를 추적할 수 있다.
| 메소드 | 내용 |
|---|---|
| Pop | 스택의 최상단에 위치한 요소를 빼내는 작업 |
| peek | 스택의 최상단에 위치한 요소를 조회 |
pop을 안 하면, 계속 같은 노드를 조회하게 된다.
스택을 왜 사용했나?
백트래킹을 위해선데, 현재 정점에서 모든 경로 탐색하다가 이전 정점으로 돌아가서 다른 경로 탐색해야 한다.
방문 배열 초기화
DFS 수행 이후, BFS 호출할 때 방문 배열 초기화를 안 했다. 각각 별도의 방문 배열을 사용하거나, 한 탐색이 끝나고 난 후에는 방문 배열을 초기화 해주어야 한다.
유기농 배추, 안전 영역에서도 그렇고 이 부분 자꾸 실수하는데 주의하자.