06. DFS/BFS 개념

다나·2023년 1월 13일

BFS DFS

코딩테스트 스터디

목록 보기

8/32

1. 그래프 (Graph) 📈

그래프는 정점(node, vertices)와 정점을 연결하는 간선(edge)으로 이루어진 자료구조이다.
그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다.
그래프를 탐색하는 방법은 대표적으로 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다.

2. 깊이 우선 탐색 (DFS = Depth-First Search)

최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동한다.
현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색한다.
스택 또는 재귀함수로 구현한다.

사진 출처 https://developer-mac.tistory.com/64

1) 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다.
2) 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
3) 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.

2-1. DFS 구현

DFS는 스택 자료구조(혹은 재귀함수)를 이용한다.

1) 탐색 시작 노드를 스택에 삽입하고 방문 처리한다.
2) 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3) 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

사진 출처 : https://code-lab1.tistory.com/15

void dfs(int x)
{
	visited[x] = true;
	cout << x << " ";
	for (int i = 0; i < graph[x].size(); i++) // 인접한 노드 사이즈만큼 탐색
	{
		int y = graph[x][i];
		if (!visited[y]) // 방문하지 않았으면 즉 visited가 False일 때 not을 해주면 True가 되므로 아래 dfs 실행
            dfs(y); // 재귀적으로 방문
	}
}

3. 너비 우선 탐색 (BFS = Breadth-First Search)

최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동한다.
주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택한다.
현재 정점에 연결된 가까운 점들부터 탐색한다.
큐를 이용해서 구현한다.

3-1. BFS 구현

void bfs(int start) {
    queue<int> q;
    q.push(start); // 첫 노드를 queue에 삽입
    visited[start] = true; // 첫 노드를 방문 처리

    // 큐가 빌 때까지 반복
    while (!q.empty()) {
        // 큐에서 하나의 원소를 뽑아 출력
        int x = q.front();
        q.pop();
        cout << x << ' ';
        // 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for (int i = 0; i < graph[x].size(); i++) {
            int y = graph[x][i];
            if (!visited[y]) {
                q.push(y);
                visited[y] = true;
            }
        }
    }
}

4. 그래프 표현 방식 👩‍🎨

인접 리스트 : O(N+E)
인접 행렬 : O(N²)
일반적으로 E(간선)의 크기가 N²에 비해 상대적으로 적다.
따라서, 인접 리스트 방식이 효율적이다.

4-1. 인접 행렬 : 2차원 배열로 그래프 표현

[i]에서 [j] 방향으로 연결이 되어 있으면 1, 아니면 0 처리를 한다.
장점 1) 구현이 쉽다.
장점 2) array[i][j]가 1인지 0인지만 확인하여 연결 여부를 확인하기 쉽다.
단점 1) 노드 [i]와 연결된 모든 노드들에 방문해보고 싶을 때 array[i][1]부터 array[i][전체노드 개수]를 모두 확인해보아야 되기 때문에 시간 복잡도가 크다.

#include <iostream>
using namespace std;

int n, m;	//노드 개수: n, 간선 개수: m
int adj[10][10];
int main() {
    cin >> n >> m;
    for (int i=0; i<m; i++) {
      int a, b;
      cin >> a >> b;
      adj[a][b] = 1;	//무방향 그래프인 경우
      adj[b][a] = 1;
    }
}

4-2. 인접 리스트 : 리스트로 그래프 표현

인접 리스트는 그래프의 연결 리스트의 자료 구조를 이용하여 구현한다.
(파이썬에서는 리스트, c++에서는 vector를 사용하여 구현)
array[i] : 노드 i에 연결된 노드들을 원소로 같는 리스트

vector<int> graph[5];

for(int i=0; i<m; i++){
	int u,v;
	cin >> u >> v;

	graph[u].push_back(v);	//무방향 그래프인 경우
	graph[v].push_back(u);
}

5. BFS / DFS 활용 문제 유형 👩‍🏫

1) 그래프의 모든 정점을 방문하는 문제
단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용해도 상관없다.

2) 경로의 특징을 저장해둬야 하는 문제
예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용한다. (BFS는 경로의 특징을 가지지 못한다.)

3) 최단거리 구해야 하는 문제
미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리하다.
왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, 너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문이다.

이밖에도