탐색 알고리즘(DFS, BFS)

📌  그래프의 기본 구조

DFS와 BFS를 공부하기 앞서, 그래프의 기본 구조를 먼저 알아보자.

그래프는 노드(Node)와 간선(Edge)로 표현되며, 이때 노드를 정점(Vertex)라고도 한다. 

그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 

또한, 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다(Adjacent)'라고 표현한다.

그래프 구조 예시

 

프로그래밍에서는 그래프를 크게 2가지 방식으로 표현할 수 있는데, 코딩 테스트에서도 필요한 개념이니 꼭 숙지하도록 하자.

예시 그래프 - 간선의 숫자는 비용을 의미

 

1.  인접 행렬(Adjacency Matrix)

2차원 배열로 그래프의 연결 관계를 표현하는 방식

인접 행렬 방식은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다. 위와 같은 예시 그래프가 있다고 했을 때, 이를 인접 행렬로 표현하면 아래 표처럼 나타낼 수 있다. 연결이 되어 있지 않은 노드끼리는 무한(Infinity)의 비용이라고 작성한다.

	0	1	2
0	0	7	5
1	7	0	무한
2	5	무한	0

이를 c++ 코드로 작성하면 다음과 같다.

#include "iostream"
#define INF 999999999

using namespace std;

int graph[3][3] = {
    {0, 7, 5},
    {7, 0, INF},
    {5, INF, 0}
};

int main(void) {
    // 그래프 출력
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cout << graph[i][j] << ' ';
        }
        cout << '\n';
    }
}

 

2.  인접 리스트(Adjacency List)

리스트로 그래프의 연결 관계를 표현하는 방식

인접 리스트 방식에서는 다음 그림처럼 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결해 저장한다.

인접 리스트 표현 예시

인접 리스트는 '연결 리스트'라는 자료구조를 이용해 구현한다. 

(*파이썬의 경우에는 그냥 리스트 자료형을 사용하면 된다.)

#include "iostream"
#include "vector"

using namespace std;

vector<pair<int, int> > graph[3];

int main(void) {
    graph[0].push_back({1, 7});
    graph[0].push_back({2, 5});

    graph[1].push_back({0, 7});

    graph[2].push_back({0, 5});

    // 그래프 출력
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < graph[i].size(); j++) {
            cout << '(' << graph[i][j].first << ',' << graph[i][j].second << ')' << ' ';
        }
        cout << '\n';
    } 
}

 

이 2가지 방식의 차이점에 대해 생각해보자.

메모리 측면에서 보자면, 인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비된다. 반면 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다.

하지만, 이러한 특성 때문에 인접 리스트 방식은 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다. 인접 리스트 방식에서는 연결된 데이터를 하나씩 확인해야 하기 때문이다. 

 

 

---

 

그럼 이제 본격적으로 DFS와 BFS에 대해 알아보자!

 

📌  DFS란?

DFS는 Depth-First Search의 약자로, 깊이 우선 탐색 알고리즘을 말한다. 즉, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 특정한 경로에서 최대한 깊은 곳까지 들어가서 제일 끝 노드(leaf node)를 방문한 뒤, 다시 뒤로 돌아가 다른 경로로 탐색한다.

DFS는 스택(Stack, LIFO Queue)를 사용한다.

 

DFS 탐색 예시

위 그림을 보면, 1번 노드부터 시작해 연결되어 있는 노드 중 가장 작은 숫자부터 깊이 우선 탐색을 하는 과정을 볼 수 있다. 색깔이 있는 숫자가 탐색 순서이다. 단계별로 스택의 변화는 1 -> 1, 2 -> 1, 2, 7 -> 1, 2, 7, 6 -> 1, 2, 7 -> 1, 2, 7, 8 -> 1, 2, 7 -> 1, 2 -> 1 -> 1, 3 -> 1, 3, 4 -> 1, 3, 4, 5 -> 1, 3, 4 -> 1, 3 -> 1 -> null 이렇게 된다. 

#include "iostream"
#include "vector"
using namespace std;

bool visited[9];
vector<int> graph[9];

void dfs(int x) {
    visited[x] = true;
    for (int i = 0; i < graph[x].size(); i++) {
        int y = graph[x][i];
        if (!visited[y]) dfs(y);
    }
}

// main 생략

 

DFS는 스택 자료구조에 기초한다는 점에서 구현이 간단하다. 실제로는 스택을 쓰지 않아도 되며 탐색을 수행함에 있어서 데이터의 개수가 N개인 경우에 O(N)의 시간이 소요된다는 특징이 있다. 또한, 재귀 함수를 이용해 구현했을 때 매우 간결하게 구현할 수 있다.

 

 

 

---

 

 

📌  BFS란?

BFS는 Breadth-First Search의 약자로, 너비 우선 탐색 알고리즘이다. 쉽게 말해 가까운 노드부터 탐색하는 알고리즘이다. 

BFS는 FIFO Queue를 이용해 구현할 수 있다.

 

BFS 탐색 예시

1번 노드부터 시작해 인접한 노드부터 탐색하기 때문에 위와 같이 탐색하게 된다. 단계별 큐의 변화는 1 -> 2, 3, 8 -> 3, 8, 7 -> 8, 7, 4, 5 -> 7, 4, 5 -> 4, 5, 6 -> 5, 6 -> 6 -> null 이렇게 된다. 

 

#include "iostream"
#include "queue"
#include "vector"
using namespace std;

bool visited[9];
vector<int> graph[9];

void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < graph[x].size(); i++) {
            int y = graph[x][i];
            if (!visited[y]) {
                q.push(y);
                visited[y] = true;
            }
        }
    }
}

// main 생략

 

DFS 역시 큐 자료구조에 기초한다는 점에서 구현이 간단하며, c++에서는 queue, python에서는 deque 라이브러리를 사용하면 된다. 탐색을 수행하는 데에 있어 O(n)의 시간이 소요되며, 일반적인 경우 실제 수행 시간은 DFS보다 좋은 편이다. 

 

 

 

---

 

 

코딩테스트 중 2차원 배열에서의 탐색 문제를 만나면 배열을 그래프 형태로 바꿔서 생각해보자.

그러면 풀이 방법을 조금 더 쉽게 떠올릴 수 있을 것이다.

예를 들어 게임 맵이 3X3 형태의 2차원 배열이고 각 데이터를 좌표라고 생각해보자. 

이때 각 좌표를 상하좌우로만 이동할 수 있다면 상하좌우가 간선으로 연결된 그래프로 생각할 수 있을 것이다. 

 

 

🔗 참고 자료

이것이 취업을 위한 코딩 테스트다 with 파이썬 : 네이버 도서