백준 1260번 : DFS와 BFS
이번 문제는 DFS와 BFS를 둘 다 사용해보는 문제이다.
정점의 개수 = n
간선의 개수 = m
시작 정점 = v
가 주어지고 그 다음으로 m개의 간선이 주어진다.
출력을 어떻게 해야할지, 로직을 어떻게 나누어야할지 생각해야하는 문제이기 때문에 기존의 탐색 알고리즘 문제와 달리 헷갈릴 수 있다.
그러나 기본적인 탐색 알고리즘의 사용법을 파악하기에는 아주 좋은 문제라고 생각한다.
전역적으로 사용할 변수를 선언한다.
1
2
3
4
5
6
public class Main {
static int[][] arr;
static StringBuilder sb = new StringBuilder();
static boolean[] visited;
static int n, m, v;
}
각각
그래프를 표현할 arr
결과 값을 출력할 sb
탐색 후 방문 여부를 체크할 visited
노드 n, 간선 개수 m, 시작 정점 v 이다.
이 변수들은 dfs 탐색, bfs 탐색 시에 전역적으로 사용하기 위해 클래스 멤버 변수로 선언한다.
그 다음 입력 받은 데이터를 가공할 로직을 작성한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void main(String[] args) throws java.io.IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
v = Integer.parseInt(st.nextToken());
arr = new int[n+1][n+1];
visited = new boolean[n+1];
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int x=Integer.parseInt(st.nextToken());
int y=Integer.parseInt(st.nextToken());
arr[x][y] = arr[y][x] = 1;
}
}
가장 먼저 입력된 노드, 간선 개수, 시작 정점을 입력 받고 정점의 개수 만큼 arr의 크기를 정하여 선언 하고 마찬가지로 방문 여부를 체크할 visited 배열의 크기 역시 지정한다.
여기서 크기는 배열이 0부터 시작하므로 1씩 더해 실질적인 마지막 정점까지로 지정한다.
이후 for문을 실행해 간선의 개수 만큼 그래프를 생성한다.
이로써 지정된 크기 만큼의 그래프가 생성된다.
그래프에서 연결된 정점은 1 아닌 정점은 0으로 표현된다.
다음으로 시작 정점을 입력 받아 dfs와 bfs 탐색을 실행한다.
두 탐색 알고리즘이 모두 실행되어야하기 때문에 각각 별개의 함수로 구현한다.
1
2
3
4
5
6
7
8
9
10
public static void dfs(int v) {
visited[v] = true;
sb.append(v).append(" ");
for (int i = 0; i <= n; i++) {
if (arr[v][i] == 1 && !visited[i]) {
dfs(i);
}
}
}
우선 dfs 탐색이다.
시작 정점은 방문 여부를 true로 변경하고 현재 정점을 StringBuilder에 저장한다.
그 다음 탐색을 시작한다.
이 탐색은 노드를 전부 순회하되,
그래프 arr[시작정점][현재정점]으로 표현하여 1이라면 두 정점이 연결되어 있는 것이고, 0이라면 연결되어 있지 않다는 것이다.
또한, 현재 도달한 정점의 방문 여부가 false로 체크되어 있다면
이 정점은 방문하지 않았으며, 연결이 되어 있다는 의미이다.
고로, 재귀를 사용하여 더욱 깊게 탐색해야한다.
재귀함수가 시작된다면, 도달한 정점이 현재 정점으로 치환되고 방문 여부는 true로 바뀐다.
또한, 도달한 정점이 sb에 합쳐지고 마찬가지로 다음 탐색을 시작하게 된다.
예를 들면 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
정점 수(n) = 5, 간선 수(m) = 4, 시작 정점(v) = 3
간선의 연결 정보
1 2
1 3
2 3
2 4
인접 행렬
1 2 3 4 5
1 [0 1 1 0 0]
2 [1 0 1 1 0]
3 [1 1 0 0 0]
4 [0 1 0 0 0]
5 [0 0 0 0 0]
DFS 탐색 순서
1. 시작 정점 3을 방문하고 방문 리스트에 추가 (방문 리스트: 3)
2. 3과 연결된 정점 중 방문하지 않은 정점 1을 방문하고 방문 리스트에 추가 (방문 리스트: 3->1)
3. 1과 연결된 정점 중 방문하지 않은 정점 2를 방문하고 방문 리스트에 추가 (방문 리스트: 3->1->2)
4. 2와 연결된 정점 중 방문하지 않은 정점 4를 방문하고 방문 리스트에 추가 (방문 리스트: 3->1->2->4)
5. 이제 더 이상 방문할 정점이 없으므로, DFS 탐색이 종료 / 최종 방문 리스트는 3->1->2->4
DFS는 시작 정점으로부터 깊이 우선으로 그래프를 탐색하기 때문에 더 이상 방문할 정점이 없을 때 까지 탐색을 계속하고, 없는 경우 이전 정점으로 돌아가서 다시 탐색을 진행한다.
이 방식을 표현하기 가장 좋은 방법이 한 가지 루트로 최대한 깊게 진행했다가 도달하면 되돌아 나와 다시 같은 방식으로 진행하는 재귀이다.
다음은 BFS 탐색이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void bfs(int v) {
Queue<Integer> q = new LinkedList<>();
q.add(v);
visited[v] = true;
while(!q.isEmpty()) {
v = q.poll();
sb.append(v).append(" ");
for (int i = 1; i <= n; i++) {
if (arr[v][i] == 1 && !visited[i]) {
q.offer(i);
visited[i] = true;
}
}
}
}
BFS는 큐를 사용한다.
시작 정점을 q에 삽입하고, 시작 정점에 해당하는 visited 인덱스를 true로 변환 한 다음 while 문을 통해 q가 빌때까지 반복문을 실행한다.
반복문 실행 흐름은 다음과 같다.
- 현재 도달한 정점을 v(시작 정점)에 저장한다.
- 도달한 정점을 sb에 합친다.
- for문을 실행시켜 1(최소 정점)부터 n(최대 정점)까지 반복한다.
- DFS 탐색과 마찬가지의 조건으로 v(시작 정점)과 i(도달한 정점)이 그래프 상에서 1이라면 연결이 되어 있는 것이고 만약 도달한 정점의 visited 인덱스가 false라면 이전에 방문하지 않았다는 뜻이기 때문에 올바른 탐색이다.
- 도달한 정점을 큐에 삽입한다. -> 이때까지 큐는 비어 있었으며 시작정점은 다시 i가 된다.
- 마찬가지로 도달한 정점을 방문 체크한다.
- while문으로 돌아가 다음 정점에 도달했기 때문에 큐에는 값이 들어있고, 이 과정을 반복한다.
예를 들면 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
정점 수(n) = 5, 간선 수(m) = 4, 시작 정점(v) = 3
간선의 연결 정보
1 2
1 3
2 3
2 4
인접 행렬
1 2 3 4 5
1 [0 1 1 0 0]
2 [1 0 1 1 0]
3 [1 1 0 0 0]
4 [0 1 0 0 0]
5 [0 0 0 0 0]
BFS 탐색 순서
1. 시작 정점 3을 방문하고 방문 리스트에 추가 (방문 리스트: 3)
2. 3과 연결된 정점 중 방문하지 않은 정점 1, 2를 차례대로 방문하고 방문 리스트에 추가 (방문 리스트: 3->1->2)
3. 이제 1과 연결된 다른 정점은 없으므로, 다음으로 2와 연결된 정점 중 방문하지 않은 정점 4를 방문하고 방문 리스트에 추가 (방문 리스트: 3->1->2->4)
4. 이제 더 이상 방문할 정점이 없으므로, BFS 탐색이 종료 / 최종 방문 리스트는 3->1->2->4
BFS는 너비 우선으로 그래프를 탐색하고, 더 이상 방문할 정점이 없을 경우 탐색이 종료된다.
다시 말해, 시작 정점으로 부터 바로 다음 연결된 정점을 이어서 탐색하는 방식으로 바로 다음 정점을 계속해서 탐색하기 위한 방법으로 Queue를 사용한다.
예시에도 있지만 순서대로 방문하지 않은 정점을 탐색한다.
이로써 DFS와 BFS 탐색 두 가지를 살펴보았고, 두 탐색의 기본을 다시 보고자 한다면 이 게시글로 돌아오면 된다.
전체 소스코드는 아래와 같다.
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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class sdf {
static int[][] arr;
static StringBuilder sb = new StringBuilder();
static boolean[] visited;
static int n, m, v;
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
v = Integer.parseInt(st.nextToken());
arr = new int[n+1][n+1];
visited = new boolean[n+1];
for (int i = 0 ; i < m; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
arr[x][y] = arr[y][x] = 1;
}
dfs(v);
sb.append('\n');
visited = new boolean[n+1];
bfs(v);
System.out.println(sb);
}
public static void dfs(int v) {
visited[v] = true;
sb.append(v).append(" ");
for (int i = 0; i <= n; i++) {
if (arr[v][i] == 1 && !visited[i]) {
dfs(i);
}
}
}
public static void bfs(int v) {
Queue<Integer> q = new LinkedList<>();
q.add(v);
visited[v] = true;
while(!q.isEmpty()) {
v = q.poll();
sb.append(v).append(" ");
for (int i = 1; i <= n; i++) {
if (arr[v][i] == 1 && !visited[i]) {
q.offer(i);
visited[i] = true;
}
}
}
}
}
솔직히 기본이라고는 했는데 이 조차도 구현하기 쉽지 않다.
하지만 그렇기 때문에 BFS, DFS 탐색 문제를 집중적으로 풀기 시작했고, 정렬 때와 마찬가지로 꾸준히 풀다보면 길이 보일 거라 생각한다.