그래프를 탐색하는 방법! DFS와 BFS
그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 이야기하며, 그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다
DFS 깊이 우선 탐색 (Depth-First Search)
루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다
시작 노드에서부터 한 경로를 따라 최대한 깊게 탐색한 후, 다른 경로를 탐색한다
DFS는 재귀호출과 스택 자료구조를 이용하여 표현된다.
1.탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문처리를 한다.
2-1. 인접 노드가 여러 개 있으면 번호가 낮은 순서부터 처리
2-2. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.Java 코드로 구현
공통 부분
public class Study {
static boolean[] visited; //방문 확인할 배열
static ArrayList<Integer> arr; //그래프 넣을 곳
static StringBuilder sb = new StringBuilder(); //출력
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken()); //정점의 개수
int m = Integer.parseInt(st.nextToken()); //간선의 개수
int v = Integer.parseInt(st.nextToken()); //탐색을 시작할 정점의 번호
visited = new boolean[n+1];
arr = new ArrayList<>();
for(int i=1; i<n+1; i++) {
arr[i] = new ArrayList<>(); //초기화 시켜주기
}
//그래프 입력 받기
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].add(y);
arr[y].add(x);
}
DFS(v);
}
}
재귀 형태로 구현
public void DFS(int v) {
visited[v] = true; //현재 노드를 방문 처리
sb.append(n).append(" ");
for(int next: arr[v]) {
if(!visited[next]) {
DFS(next);
}
}
}
스택으로 구현하기
public void DFS(int v) {
Stack<Integer> stack = new Stack<>();
//시작 노드를 스택에 넣기
stack.push(v);
//시작 노드 방문처리
visited[v] = true;
while(!stack.isEmpty()) {
int index = stack.pop();
sb.append(index).append(" ");
for(int next : arr[v]) {
if(!visited[next]) {
stack.push(next);
visited[next] = true;
}
}
}
} DFS 특징
- 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
- 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함
- 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림
BFS 너비 우선 탐색 (Breadth-First Search)
루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로, 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 탐색 방법을 말한다
BFS는 큐 자료구조를 이용하여 표현된다
1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.자바 코드로 구현
public class Study {
static boolean[] visited; //방문 확인할 배열
static ArrayList<Integer> arr; //그래프 넣을 곳
static StringBuilder sb = new StringBuilder(); //출력
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken()); //정점의 개수
int m = Integer.parseInt(st.nextToken()); //간선의 개수
int v = Integer.parseInt(st.nextToken()); //탐색을 시작할 정점의 번호
visited = new boolean[n+1];
arr = new ArrayList<>();
for(int i=1; i<n+1; i++) {
arr[i] = new ArrayList<>(); //초기화 시켜주기
}
//그래프 입력 받기
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].add(y);
arr[y].add(x);
}
BFS(v);
}
public void BFS(int v) {
Queue<Integer> Queue = new LinkedList<>();
queue.offer(v);
visited[v] = true;
while(!queue.isEmpty()) {
int now = queue.poll();
sb.append(now).append(" ");
for(int next : arr[now]) {
if(!visited[next]) {
visited[next] = true;
queue.add(next);
}
}
}
}
}
BFS 특징
- 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택한다
DFS와 BFS 비교
| DFS | BFS | |
|---|---|---|
| 탐색과정 | 현재 정점에서 갈 수 있는 끝까지 방문하여 탐색 | 현재 정점에서 연결된 가까운 점들부터 탐색 |
| 구현 방법 | 스택, 재귀 함수 | 큐 |
| 장점 | 그래프의 깊이가 깊을수록 빠름 | 찾는 노드가 인접할수록 빠름 |
| 단점 | 메모리가 적음 | 노드가 많을수록 메모리를 많이 소비 |
| 적용 | 경로의 특징을 저장해야 하는 경우 / 길 찾기 / 미로 문제 | 길 찾기, 라우팅 / 웹 크롤러 / 소셜 네트워크에서 멀리 떨어진 사람 찾기 / 그래프에서 주변 위치 찾기 |
DFS와 BFS를 활용할 문제 유형들
1. 그래프의 모든 정점을 방문
-> DFS / BFS 둘 다 상관 없음
2. 경로의 특징을 저장해둬야 하는 문제
-> DFS (순서대로 탐색하기 때문, BFS는 경로의 특징을 가지지 못함)
3. 최단거리 구해야 하는 문제
-> BFS (너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시, 먼저 찾아지는 해답이 곧 최단거리!)
DFS와 BFS 추천 문제!
📌 DFS, BFS 이해했다면 풀어보면 좋은 문제
📌 어려웠지만 풀면서 맛있었던 문제 :)
ᴘʜɪʟɪᴘᴘɪᴀɴs 3:14