알고리즘 : DFS와 BFS (1) - DFS (C++로 구현)

참고 영상 : https://youtu.be/7C9RgOcvkvo?si=PuM-7RIBWbVPtYTw 

 

bfs와 dfs는 탐색 알고리즘이다. 내가 헷갈렸던 부분이 있는데 그래프를 인접 행렬, 인접 리스트로 표현할 수 있다고 배웠는데 bfs, dfs는 각각 큐랑 스택을 사용하여 구현한다는 점이었다.

bfs와 dfs는 그래프를 탐색하는 알고리즘인 것이다. 그래프를 표현하는 방식이 아니다!

 

https://shine-slowly.tistory.com/39

알고리즘 : 자료구조(1) 스택 (Stack) (C++로 구현)

https://shine-slowly.tistory.com/40

알고리즘 : 자료구조(2) 큐 (Queue) (C++로 구현)

 

큐와 스택을 아예 모른다면 위 티스토리를 참고하는 것을 추천한다. 대충 안다면 아래에 짧게 설명하는 거만 읽어도 된다.

 

스택 (Stack)

선입후출(FILO) 형식의 자료구조로 입구와 출구과 동일한 형태이다.

#include <stack>
stack<int> stack;
stack.push(5); // 데이터 추가
stack.pop(); // 데이터 삭제

c++에서는 이와 같이 사용한다.

 

 

큐 (Queue)

선입선출(FIFO) 형식의 자료구조로 입구와 출구가 모두 존재한다. 

#include <queue> 
queue<int> q;
q.push(5); // back 데이터추가
q.pop(); // front 데이터삭제

c++에서는 이와 같이 사용한다.

 

 

재귀함수 (Recursive Function)

자기 자신을 다시 호출하는 함수를 재귀 함수라고 한다. while문이나 for문을 사용하지 않아도 무한대로 호출이 가능하다.

void recursive(int i) {
	if (i == 5) {
		cout << "도달했습니다!\n";
		return;
	}
	cout << i << "에서 " << i + 1 << "를 호출합니다.\n";
	recursive(i+1);
	cout << i << "를 종료합니다.\n";
}
int main() {
	recursive(1);
}

재귀함수를 이해할 수 있는 간단한 코드이다. 

 

int gcd(int x, int y) {
    if (x % y == 0)
        return y;
    else
        return gcd(y, x % y);
}

유클리드 호제법의 코드이다. 필요한 경우 자신을 다시 호출하여 재귀적으로 계산을 수행하게 된다. 

 

 

 

 

DFS (Depth-First Search, 깊이우선탐색)

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택 자료구조(or 재귀함수)를 이용한다.

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

 

위 그래프를 이용해서 DFS 동작 방식을 살펴보도록 하겠다. 시작 노드는 1이며 방문 기준은 번호가 낮은 인접 노드부터로 설정하였다.

 

[Step 1] 시작 노드인 '1'을 스택에 삽입하고 방문처리를 한다.

 

[Step 2] 스택의 최상단 노드인 '1'에 방문하지 않은 인접노드 '2', '3', '8'이 있다. 이 중 가장 작은 노드인 '2'를 스택에 넣고 방문처리를 한다. 

 

[Step 3] 스택의 최상난 노드인 '2'에 방문하지 않은 인접노드 '7'이 있다. 따라서 '7'번 노드를 스택에 넣고 방문처리를 한다. 

 

[Step 4] 스택의 최상단 노드인 '7'에 방문하지 않은 인접노드 '6', '8'이 있다. 이중 가장 작은 노드인 '6'을 스택에 넣고 방문처리를 한다.

 

[Step 5] 스택의 최상단 노드인 '6'에 방문하지 않은 인접 노드가 없다. 따라서 스택에서 '6'번 노드를 꺼낸다.

 

[Step 6] 스택의 최상단 노드인 '7'에 방문하지 않은 인접 노드 '8'이 있다. 따라서 '8'번 노드를 스택에 넣고 방문처리를 한다.

 

 

#include<iostream>
#include<vector>
using namespace std;
bool visited[9]; // 전역으로 선언하면 모두 false
vector<int> graph[9];
void dfs(int x) {
    visited[x] = true;
    cout << x << ' ';
    for (int i = 0; i < graph[x].size(); i++)
    {
        if (!visited[graph[x][i]])  // 방문하지 않았다면
            dfs(graph[x][i]);
    }
}

int main() {
    // 노드 1에 연결된 노드 정보 저장
    graph[1].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(8);

    // 노드 2에 연결된 노드 정보 저장 
    graph[2].push_back(1);
    graph[2].push_back(7);

    // 노드 3에 연결된 노드 정보 저장 
    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[3].push_back(5);

    // 노드 4에 연결된 노드 정보 저장 
    graph[4].push_back(3);
    graph[4].push_back(5);

    // 노드 5에 연결된 노드 정보 저장 
    graph[5].push_back(3);
    graph[5].push_back(4);

    // 노드 6에 연결된 노드 정보 저장 
    graph[6].push_back(7);

    // 노드 7에 연결된 노드 정보 저장 
    graph[7].push_back(2);
    graph[7].push_back(6);
    graph[7].push_back(8);

    // 노드 8에 연결된 노드 정보 저장 
    graph[8].push_back(1);
    graph[8].push_back(7);

    dfs(1);
}

위 그래프를 c++로 표현해보았다. 방문하지 않은 노드가 있다면 방문하고 인접 노드를 또 찾으며 (재귀 사용) 반복한다. 방문할 노드가 없으면 dfs 함수가 끝나게 되고 그 전단계로 돌아간다.

 

void dfs_stack(int start) {
    stack<int> s;
    visited[start] = true;
    s.push(start);
    cout << start << ' ';
    while (!s.empty()) {
        int x = s.top();
        for (int i = 0; i < graph[x].size(); i++)
        {
            if (!visited[graph[x][i]]) {
                visited[graph[x][i]] = true;
                s.push(graph[x][i]);
                cout << graph[x][i] << ' ';
                break;
            }
            if (i == graph[x].size() - 1)
                s.pop();
        }
    }
}

stack을 이용해서 구현하는 방법이다.

 

 

BFS는 다음 포스팅에서 이어서 설명하도록 하겠다 ^.^