[1260] DFS와 BFS
그래프 탐색 기초인 DFS & BFS 를 배우기 가장 좋은 문제라고 생각한다.
다른 조건을 생각하지 않고 기본에 충실할 수 있기 때문!
예제 입력 풀이부터 보자
예제 입력 1
4 5 1
1 2
1 3
1 4
2 4
3 4
4 5 1
숫자(노드)는 1부터 4까지 총 4개
연관 관계(간선)가 5번 주어짐
탐색할 시작 숫자는 1임
1 2
1 3
1 4
2 4
3 4
1 에서 2 를 갈 수 있음
1 에서 3 을 갈 수 있음
1 에서 4 를 갈 수 있음
2 에서 4 를 갈 수 있음
3 에서 4 를 갈 수 있음
이렇게 그려진 연관관계는 여러 방법으로 표현할 수 있다.
(2차원 배열, ArrayList배열 등등)
필자는 ArrayList[ ]로 구현한다.
자, 이렇게 갈 수 있다는 것도 알았고 입력도 잘 받았다. 어떻게 탐색하는지 알아보자
연결된 모습!
주의사항
단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다
작은 것부터 방문하는 것이 중요하다.
1 에서 갈 수 있는 숫자는 2,3,4 인데
3 or 4 부터 탐색하지 말고 가장 작은 숫자인 2 부터 탐색하라는 뜻이다.
또 방향이 주어지지 않았기 때문에 양방향으로 푼다
(1 3 이 주어지면 1에서도 3을, 3에서도 1을 갈 수 있다)
DFS 라면?
깊이를 우선으로 탐색한다면..?
시작 번호는 1 이다
- 1 에서 2 를 탐색한다.
- 2 에서 4 를 탐색한다.
- 4 에서 3 를 탐색한다.
- 3 에서 탐색할 수 있는 숫자가 없으므로 종료된다.
이미 탐색을 했거나 더 이상 탐색할 숫자가 없다면 돌아간다.
1에서 2,3,4를 갈 수 있지만 2를 먼저 탐색한다.
2에서 4를 가고 4에서 3을 간다.
더이상 탐색할 수 있는 숫자가 없으므로 종료.
예제 그림! 숫자를 순서로 탐색한다!
BFS 라면?
너비를 우선으로 탐색한다면..?
시작 번호는 1 이다
- 1 에서 2 를 탐색한다.
- 1 에서 3 를 탐색한다.
- 1 에서 4 를 탐색한다.
- 더 이상 탐색할 수 있는 숫자가 없으므로 종료된다.
시작 숫자인 1과 연결된 모든 숫자를 탐색하고 이후 숫자를 기준으로 탐색하는 방식인데
해당 예제는 1이 모든 숫자와 연결되어 있어 여기서 종료된다.
(만약 숫자가 7까지 있고 2에서 5,6,7을 갈 수 있다면 3번 로직 이후 2번 기준으로 5,6,7을 찾고 종료된다)
예제 그림! 숫자를 순서로 탐색한다!
준비물
그래프 탐색(DFS&BFS)을 위한 준비물은 다음과 같다.
방문했는지 확인해 줄 boolean[]
간선 정보를 담을 ArrayList[]
코드
package velog;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BaekJoon1260 {
private static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
private static final StringBuilder result = new StringBuilder();
private static List<Integer>[] list;
private static boolean[] DFSVisited;
private static boolean[] BFSVisited;
public static void main(String[] args) throws IOException {
StringTokenizer st = new StringTokenizer(BR.readLine());
int N = Integer.parseInt(st.nextToken()) + 1;
int M = Integer.parseInt(st.nextToken());
int startIndex = Integer.parseInt(st.nextToken());
list = new ArrayList[N];
DFSVisited = new boolean[N];
BFSVisited = new boolean[N];
for (int i = 0; i < N; i++) {
list[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(BR.readLine());
int firstIndex = Integer.parseInt(st.nextToken());
int secondIndex = Integer.parseInt(st.nextToken());
list[firstIndex].add(secondIndex);
list[secondIndex].add(firstIndex);
Collections.sort(list[firstIndex]);
Collections.sort(list[secondIndex]);
}
DFS(startIndex);
result.append(System.lineSeparator());
BFS(startIndex);
System.out.println(result);
}
private static void DFS(int startIndex) {
if (DFSVisited[startIndex]) {
return;
}
DFSVisited[startIndex] = true;
result.append(startIndex)
.append(" ");
for (int newIndex : list[startIndex]) {
if (!DFSVisited[newIndex]) {
DFS(newIndex);
}
}
}
private static void BFS(int startIndex) {
Queue<Integer> queue = new LinkedList<>();
queue.add(startIndex);
while (!queue.isEmpty()) {
int index = queue.poll();
if (!BFSVisited[index]) {
result.append(index)
.append(" ");
BFSVisited[index] = true;
}
for (int newIndex : list[index]) {
if (!BFSVisited[newIndex]) {
queue.add(newIndex);
}
}
}
}
}
