깊이 우선 탐색 (Depth-First Search) : 깊이가 깊은 것부터 탐색하는 것. 같은 깊이의 노드가 여러 개 있으면 일단 현재 노드의 자식 노드들을 전부 탐색하고 그 다음에 나머지를 탐색해준다.
1. 깊이 우선 탐색이므로 일단 a에서 마지막 깊이까지 탐색을 해준다. 현재 탐색 중인 노드에 자식 노드가 몇 개가 있든 일단 깊이 순으로 탐색해준다. (a - b - d - g)
2. g까지 탐색을 끝냈으면, 이제 b의 자식 노드 중 탐색하지 않았던 e를 다시 깊이 우선 탐색 해준다. (e - h - i)
3. 마지막으로 a의 자식 노드 중 탐색하지 않았던 c를 다시 깊이 우선 탐색 해준다. (c - f)
너비 우선 탐색 (Breadth-First Search) : 같은 깊이 상에 있는 노드 중 가장 왼쪽부터 오른쪽까지 탐색하면서 내려가는 것. 자식 노드가 있어도 일단 상위 깊이에 있는 노드들을 전부 탐색한 후 자식 노드들의 집합을 탐색해준다.
따로 정리 할 필요 없이 a부터 그 다음 깊이를 계속 탐색해주면 된다.
(a - (b - c) - (d - e - f) - (g - h - i))
DFS와 BFS를 이용하기 위해선 인접행렬과 인접리스트를 알아야한다.
1. 인접행렬 : 노드의 연결 관계를 이차원 배열로 표현한 것이다. 노드 간에 연결이 되어있으면 1, 그렇지 않으면 0으로 표현한다. (자기 자신도 0. 간선이 존재해야한다.) 위의 그래프를 예로 들어보자.
//방향이 있을 경우 (자식 노드 쪽으로) //방향이 없을 경우
a b c d e f g h i a b c d e f g h i
a 0 1 1 0 0 0 0 0 0 a 0 1 1 0 0 0 0 0 0
b 0 0 0 1 1 0 0 0 0 b 1 0 0 1 1 0 0 0 0
c 0 0 0 0 0 1 0 0 0 c 1 0 0 0 0 1 0 0 0
d 0 0 0 0 0 0 1 0 0 d 0 1 0 0 0 0 1 0 0
e 0 0 0 0 0 0 0 1 1 e 0 1 0 0 0 0 0 1 1
f 0 0 0 0 0 0 0 0 0 f 0 0 1 0 0 0 0 0 0
g 0 0 0 0 0 0 0 0 0 g 0 0 0 1 0 0 0 0 0
h 0 0 0 0 0 0 0 0 0 h 0 0 0 0 1 0 0 0 0
i 0 0 0 0 0 0 0 0 0 i 0 0 0 0 1 0 0 0 0
이 때 방향이 없는 그래프는 (a, a), (b, b), ... , (i, i)에 대해 대칭이 된다.
구현은 쉽지만 노드의 개수가 많아지면 넣어야 할 자료의 양도 상대적으로 커지게 된다.
2. 인접리스트 : 인접행렬은 배열로 저장했다면, 인접리스트는 연결되는 노드를 리스트에 넣어서 정리한 것이다. 즉 인접행렬은 배열에 1, 0을 저장해서 연결 관계를 전부 표현했지만, 인접리스트는
a = ( c, d )
b = ( e, f )
c = ( g )
...
와 같이 특정 노드에 연결되어 있는 노드만 저장해준 것이다. 이렇게 저장해줄 경우 상대적으로 메모리를 효율적으로 사용할 수 있게 된다. 즉 DFS나 BFS를 만들 때 인접리스트를 이용하는게 효율면에서는 더 좋다.
인접리스트를 이용하여 백준의 [1260. DFS와 BFS]를 구현해보자.
1260. DFS와 BFS
문제
https://www.acmicpc.net/problem/2178
풀이
위의 내용을 구현하기 위해선 재귀 + 큐 + list를 이용한다. 주석으로 설명을 달아놨지만 기본적인 구현 설명을 해보겠다.
1. Visited 배열은 방문 여부를 확인하기 위해 존재하는데, 간선이 양방향이기 때문에 방문 여부를 설정하지 않으면 인접리스트에서 이미 방문했던 것까지 다시 방문해서 탐색해버리기 때문에 설정을 해줘야한다.
2. DFS는 기본적인 재귀방식으로 구현할 수 있다.
DFS의 매개변수로 들어오는 x 값은 현재 방문 중이니 방문 여부를 true로 바꿔주고, 자식 노드 중에 방문을 하지 않은 노드가 있으면 선택을 하여 재귀를 통해 깊이 우선 탐색을 다시 실행시켜준다. main 함수에서 노드 번호를 오름차순으로 정렬해줬기 때문에, 낮은 번호의 탐색이 끝나면 그 다음 번호의 노드를 탐색할 수 있게 해줬다.
3. BFS는 큐를 이용하여 구현할 수 있다.
현재 노드의 자식 노드를 전부 탐색하면서, 현재 노드의 자식노드가 자식노드를 가지고 있을 경우, 탐색 대상으로 취급하여 Search 큐에 삽입한다. 이렇게 구현하면 현재 노드의 자식 노드 탐색이 전부 끝날 때, 이들의 자식 노드들이 큐에 모두 담겨 있을 것이다. 이를 큐가 비게 될 때 (마지막 leaf 노드까지 전부 탐색할 때)까지 반복해준다.
4. 주석에 써놓았지만 vector는 sort(vector.begin(), vector.end(), compare)로, 배열은 sort(array, array + array.size() - 1, compare)로 정렬할 수 있으며, list는 list.sort(compare)로 정렬할 수 있다.
소스코드
//
// DFSorBFS.cpp
// test
//
// Created by 신기열 on 31/05/2019.
// Copyright © 2019 신기열. All rights reserved.
//
#include <stdio.h>
#include <queue>
#include <list>
#include <algorithm>
#include <iostream>
using namespace std;
list<int> Adj[1001];
bool Visited[1001];
//DFS
void DFS(int x){
//x번 노드는 방문했으니까 true
Visited[x] = true;
cout << x << " ";
list<int>::iterator iter;
//x번의 인접리스트를 전부 돌면서 x의 자식 노드 중 방문한 적 없는 노드가 있으면 그 노드를 깊이 우선 탐색 실행 (재귀)
for(iter = Adj[x].begin(); iter != Adj[x].end(); iter++){
if(!Visited[*iter]) DFS(*iter);
}
}
//BFS
void BFS(int x){
queue Search;
//Visited 전부 false로 초기화
//문제 순서가 DFS -> BFS이고 DFS에서 Visited를사용했으니 여기서 초기화해주는 것
for(int i = 1; i <= 1000; i++){
Visited[i] = false;
}
//x 방문여부
Visited[x] = true;
Search.push(x);
//탐색해야하는 노드가 존재하지 않을 때까지는 계속 탐색해주기
while(!Search.empty()){
int q = Search.front();
Search.pop();
cout << q << " ";
//Search 대상인 노드의 자식 노드 중 방문한 적이 없는 노드가 있으면 그 노드를
//Search 대상에 포함시켜놓는 작업 반복 (Search queue에 push)
list<int>::iterator iter;
for(iter = Adj[q].begin(); iter != Adj[q].end(); iter++){
if(!Visited[*iter]){
Visited[*iter] = true;
Search.push(*iter);
}
}
}
}
int main(){
int N, M, V;
cin >> N >> M >> V;
for(int i = 0; i < M; i++){
int parent, child;
cin >> parent >> child;
//간선이 양방향임
Adj[parent].push_back(child);
Adj[child].push_back(parent);
}
for(int i = 1; i <= N; i++){
//문제에서 정점의 번호 크기가 작은 것부터 탐색한다고 했으므로 정렬해줌.
//참고로 vector나 배열은 sort(v.begin(), v.end()) 나 sort(a, a++) 꼴이지만
//list의 정렬 방법은 아래와 같다.
Adj[i].sort();
}
DFS(V);
cout << '\n';
BFS(V);
cout << '\n';
return 0;
}
소스코드 : https://github.com/betterafter/BaekJoon/blob/master/DFSorBFS/DFSorBFS.cpp
댓글
댓글 쓰기