[알고리즘] DFS & BFS 깊이우선탐색과 너비우선탐색

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

깊이우선탐색은 캐쥬얼하게 말하자면 깊이 들어갈 수 있을 만틈 들어갔다가 더 이상 들어갈 수 없을 때 뒤로 빠져나와 다른 길로 깊이 들어갔다 나왔다 하는 것을 반복하는 방법이라고 할 수 있다.

말로만 들어서는 어려우니 그림을 보면서 이해해보자.

우선 노드의 인덱스가 0부터 7까지 존재하는 그래프를 생각해보자. 각각의 노드들은 서로 다른 노드들과 연결되어 있는데, 이해의 편의를 위해서 가운데처럼 Adjacency List로 만들어보았다. 인덱스가 0인 노드는 인덱스가 1과 2인 노드들과 연결되어 있고, 인덱스가 1인 노드는 인덱스가 0, 3, 4인 노드들과 연결되어 있다. 

 

LIFO(Last In First Out)구조인 스택을 이용하면 DFS를 이해하기 쉽다.

먼저 시작 노드를 0으로 잡았을 때, 0을 빈 스택 안에 넣는다. 그리고 0에 방문 표시를 해준다.

(현재 스택의 상태 [ 0 ]) (지금껏 방문한 노드의 순서 : 0)

 

그리고 0과 인접한 노드 중에서 가장 인덱스가 작은 노드를 찾아서 스택 안에 집어넣는다. 고로 여기서는 1이 되겠다. 1에도 방문 표시를 해주면 된다.

(현재 스택의 상태 [ 0, 1 ]) (지금껏 방문한 노드의 순서 : 0, 1 )

 

그 다음에 스택 안에 들어있는 1과 인접한 노드 중에서 아직 방문하지 않은 노드들 중 가장 인덱스가 가장 작은 노드를 골라서 스택에 넣으면 된다. 1과 인접한 노드는 0, 3, 4인데 0은 아까 방문을 했으니 제외하고 그 다음 작은 노드인 3을 스택에 집어넣는다. 마찬가지로 3에도 방문표시를 해준다. 그렇게 되면 스택 안에 0, 1, 3 순서대로 쌓이게 된다. 그 다음으로 가보자.

(현재 스택의 상태 [ 0, 1, 3 ]) (지금껏 방문한 노드의 순서 : 0, 1, 3 )

 

3과 인접한 노드들 중 아직 방문하지 않았으며, 개중 가장 작은 인덱스를 가진 7을 집어넣을 수 있다. 그리고 7에 방문표시를 해준다.

(현재 스택의 상태 [ 0, 1, 3, 7 ]) (지금껏 방문한 노드의 순서 : 0, 1, 3, 7)

 

7과 인접한 노드들 중 아직 방문하지 않았으며, 개중 가장 작은 인덱스를 가진 녀석은 4이다. 그러므로 4를 스택에 집어넣고 방문표시를 한다.

현재 스택의 상태 [ 0, 1, 3, 7, 4 ]) (지금껏 방문한 노드의 순서 : 0, 1, 3, 7, 4)

 

4와 인접한 노드들을 훑어보니 1과 7인데 이미 방문표시가 모두 되어 있다. 그렇다면 4를 pop한다.

현재 스택의 상태 [ 0, 1, 3, 7 ]) (지금껏 방문한 노드의 순서 : 0, 1, 3, 7, 4)

 

4가 pop된 상황에서 스택의 top은 7일 것이다. 그럼 다시 7과 인접한 노드들 중에서 방문하지 않았으며 가장 작은 인덱스를 가진 노드를 찾게 되면 바로 5가 되겠다. 고로 5를 스택에 집어넣고 방문표시를 해준다. 

현재 스택의 상태 [ 0, 1, 3, 7, 5 ]) (지금껏 방문한 노드의 순서 : 0, 1, 3, 7, 4, 5)

 

5와 인접한 노드들은 2와 7인데 2는 아직 방문이 안됐으므로 2를 스택 안에 집어넣고 방문표시를 한다.

현재 스택의 상태 [ 0, 1, 3, 7, 5, 2 ]) (지금껏 방문한 노드의 순서 : 0, 1, 3, 7, 4, 5, 2)

 

2와 인접한 노드들은 0, 5, 6인데 0과 5는 이미 방문했으니 6을 스택 안에 집어 넣고 방문 표시를 한다.

현재 스택의 상태 [ 0, 1, 3, 7, 5, 2, 6 ]) (지금껏 방문한 노드의 순서 : 0, 1, 3, 7, 4, 5, 2, 6)

 

그렇게 되면 모든 노드에 방문표시가 되어있게 된다. 결국 지금껏 방문한 노드의 순서를 출력하면 그것이 바로 DFS가 된다.

DFS : 0, 1, 3, 7, 4, 5, 2, 6

 

그럼 이제 DFS를 코드로 구현해보자.

DFS를 구현하는 유명한 방법에는 크게 두 가지가 있다. 첫번째는 재귀, 두번째는 스택을 이용하는 것이다. 지금 그 두 가지 방법을 모두 소개해보려고 한다.

1) 재귀를 이용하여 구현하는 방법

bool visited[8];	//방문표시를 위한 배열
vector<int> graph[8];	//그래프를 입력받기 위한 정수 벡터 2차원 배열

void DFS_Recursive(int x){	
    visited[x] = true;	//인자로 받은 인덱스 노드를 방문표시
    cout << x << ' ';	//방문한 인덱스 노드를 출력
    for(int i = 0; i < graph[x].size(); i++)	//x와 인접한 노드를 순회
    {
        int y = graph[x][i];	//y에 x와 인접한 노드를 대입
        if(!visited[y])	//만약 y가 방문표시가 되어있지 않다면(즉, x와 인접한 노드 중 방문표시가 되어있지 않은 노드일 때)
            DFS_Recursive(y);	//y를 인자로 DFS함수 재귀호출
    }
}

 

결과 :

2) 스택을 이용하여 구현하는 방법

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

bool isdone(){	//모든 노드를 방문했는지 파악하기 위한 함수
    bool end = false;	//초기값을 false로 설정
    for(bool n : visited){	//visited 배열을 순회하는 범위 기반 for문
        if(n == true)	//visited의 원소가 true일 때만 계속 순회
            end = true;	//end를 true로 변경
        else	//visited의 원소 중 하나라도 false가 있을 경우 아직 모두 순회가 된 것이 아니므로
        {
            end = false;	//end를 false로 설정
            break;	//반복문 탈출
        }
    }
    if(end)	//만약 visited 배열의 원소가 전부 true라면 모든 노드가 순회된 것이므로
        return true;	//true값 반환
    else	//모든 노드가 순회되지 않았을 때
        return false;	//false값 반환
}


void DFS_Stack(int start){
    visited[start] = true;	//시작 노드를 방문표시.
    cout << start << " ";	//시작 노드 출력
    stack<int> st;	//정수형 스택 선언
    st.push(start);	//스택에 시작 노드를 집어넣음
    while(true){	//무한 루프 설정
        int y = st.top();	//y에 스택의 top을 대입
        visited[y] = true;	//스택의 top에 있는 숫자를 인덱스로 가지는 노드에 방문표시
        for(int i = 0; i < graph[y].size(); i++)	//y와 인접한 노드들을 순회
        {
            int next = graph[y][i];	//인접한 노드를 next 변수에 대입
            if(!visited[next])	//만약 아직 방문하지 않은 노드라면
            {
                st.push(next);	//스택에 집어넣기
                cout << next << " ";	//출력
                break;	//계속 y와 인접한 노드들이 스택에 삽입되면 안되므로 하나가 삽입되면 break문으로 탈출
            }
            if(visited[graph[y][graph[y].size()-1]] == true)	//만약 인접한 모든 노드들이 방문되었다면 
            {
                st.pop();	//더 이상 갈 곳이 없으므로 맨 위의 원소 pop
                break;	//break
            }
        }
        if(isdone())	//만약 모든 노드가 방문되었다면
            break;	//탈출
    }
}

결과 :

* 스택을 활용해서 만드는 것보다는 재귀를 활용하는 것이 더 깔끔하기는 하다. 

+ 메인 함수 코드)

int main(void) {
    // 노드 0에 연결된 노드 정보 저장
    graph[0].push_back(1);
    graph[0].push_back(2);
    
    // 노드 1에 연결된 노드 정보 저장
    graph[1].push_back(0);
    graph[1].push_back(3);
    graph[1].push_back(4);
    
    // 노드 2에 연결된 노드 정보 저장
    graph[2].push_back(0);
    graph[2].push_back(5);
    graph[2].push_back(6);
    
    // 노드 3에 연결된 노드 정보 저장
    graph[3].push_back(1);
    graph[3].push_back(7);
    
    // 노드 4에 연결된 노드 정보 저장
    graph[4].push_back(1);
    graph[4].push_back(7);
    
    // 노드 5에 연결된 노드 정보 저장
    graph[5].push_back(2);
    graph[5].push_back(7);
    
    // 노드 6에 연결된 노드 정보 저장
    graph[6].push_back(2);
    graph[6].push_back(7);
    
    // 노드 7에 연결된 노드 정보 저장
    graph[7].push_back(3);
    graph[7].push_back(4);
    graph[7].push_back(5);
    graph[7].push_back(6);
    
    //DFS_Recursive(0);
    //DFS_Stack(0);
    return 0;
}

2) BFS(Breadth-First Search) 너비우선탐색

BFS는 너비우선탐색의 준말로, 인접한 노드를 모두 방문하고 다른 노드로 넘어가 또 인접한 노드를 모두 방문하는 형태를 지닌다. 

LIFO(Last In First Out)의 성질을 가지고 있는 스택을 이용했던 DFS와는 다르게 BFS에서는 FIFO(First In First Out) 성질을 지닌 큐를 이용하면 이해가 쉬워진다.

그림을 통해서 이해해보자.

 

 

DFS와의 차이를 확연하게 보이기 위해서 같은 그래프를 사용한다. 따라서 Adjacency List도 동일함을 알 수 있다.

 

이제 빈 큐에 시작 노드를 삽입한다. 그리고 시작 노드를 방문처리 해준다.

(현재 큐의 상태 [ 0 ]) (지금껏 방문한 노드의 순서 : 0 )

 

다시 큐에서 시작 노드를 pop한 후에, 시작 노드와 인접한 모든 노드들을 큐에 순서대로 삽입한다. 그리고 인접 노드들을 모두 방문처리 해준다.

(현재 큐의 상태 [ 1, 2 ]) (지금껏 방문한 노드의 순서 : 0, 1, 2)

 

현재 큐 중에서 더 먼저 들어온 1을 pop하고, 1의 인접 노드들 중 아직 방문처리 되지 않은 3과 4를 큐에 삽입하고 방문처리해준다.

(현재 큐의 상태 [ 2, 3, 4 ]) (지금껏 방문한 노드의 순서 : 0, 1, 2, 3, 4)

 

또 큐에서 먼저 들어온 2를  pop하고 2의 인접 노드들 중 아직 방문처리 되지 않은 5와 6을 삽입하고 방문처리 해준다.

(현재 큐의 상태 [ 3, 4, 5, 6 ]) (지금껏 방문한 노드의 순서 : 0, 1, 2, 3, 4, 5, 6)

 

남아있는 큐 중에 가장 먼저 들어온 3을 pop하고 남아있는 3의 인접노드들 중 방문처리 되지 않은 7을 삽입하고 방문처리 한다.

(현재 큐의 상태 [ 4, 5, 6, 7 ]) (지금껏 방문한 노드의 순서 : 0, 1, 2, 3, 4, 5, 6, 7)

*사실 여기서 이미 모든 노드의 순회를 마쳤지만 큐가 모두 비어있을 때 반복문이 종료된다고 생각하면, 조금 더 진행될 필요가 있다

 

또 남아있는 큐 중에서 가장 먼저 들어온 4를 pop하고 남아있는 인접 노드들을 보니 이미 1과 7 모두 방문처리 되어있는 것을 알 수 있다. 그러므로 지금껏 방문한 노드의 순서에는 변함이 없고 큐에서는 4만 pop이 될 뿐이다.

(현재 큐의 상태 [ 5, 6, 7 ]) (지금껏 방문한 노드의 순서 : 0, 1, 2, 3, 4, 5, 6, 7)

 

마찬가지로 5를 pop하고 남아있는 인접 노드들을 보니 2와 7 모두 방문처리가 되어있다. 고로 방문한 노드 순서에는 변경이 없고 큐에서 5만 pop이 된다.

(현재 큐의 상태 [ 6, 7 ]) (지금껏 방문한 노드의 순서 : 0, 1, 2, 3, 4, 5, 6, 7)

 

6도 pop을 하게 되면 역시 인접 노드인 2와 7 모두 방문처리가 되어있다. 

(현재 큐의 상태 [ 7 ]) (지금껏 방문한 노드의 순서 : 0, 1, 2, 3, 4, 5, 6, 7)

 

마지막으로 7을 pop하게 되면 인접 노드인 3, 4, 5, 6 모두 방문처리가 되어있다. 

(현재 큐의 상태 [  ]) (지금껏 방문한 노드의 순서 : 0, 1, 2, 3, 4, 5, 6, 7)

 

결과적으로 큐는 비게 되고, 지금껏 방문한 노드의 순서는 0, 1, 2, 3, 4, 5, 6, 7이므로 BFS의 결과는 0, 1, 2, 3, 4, 5, 6, 7과 같다.

 

그럼 이제 실제 코드로 이를 구현해보자. 

bool visited[9];	//방문처리를 위한 배열
vector<int> graph[9];	//그래프를 나타내기 위한 정수형 벡터 2차원 배열

void BFS(int start){	//시작 노드를 인자로 받음
    queue<int> q;	//큐 생성
    q.push(start);	//큐에 시작 노드를 삽입
    visited[start] = true;	//시작 노드 방문처리
    while(!q.empty())	//큐가 비어있지 않는 동안만 루프
    {
        int x = q.front();	//x에 큐의 맨 앞을 대입
        q.pop();	//큐의 맨 앞을 pop
        cout << x << " ";	//x 출력
        for(int i = 0; i < graph[x].size(); i++)	//맨 앞 노드와 인접한 노드들을 순회하는 반복문
        {
            int y = graph[x][i];	//y에 x와 인접한 노드들을 대입
            if(!visited[y])	//아직 y에 방문처리가 되어있지 않을 때
            {
                q.push(y);	//큐에 y를 삽입
                visited[y] = true;	//y에 방문처리
            }
        }
    }
}

결과 :

+메인함수 코드)

int main(void) {
    // 노드 0에 연결된 노드 정보 저장
    graph[0].push_back(1);
    graph[0].push_back(2);
    
    // 노드 1에 연결된 노드 정보 저장
    graph[1].push_back(0);
    graph[1].push_back(3);
    graph[1].push_back(4);
    
    // 노드 2에 연결된 노드 정보 저장
    graph[2].push_back(0);
    graph[2].push_back(5);
    graph[2].push_back(6);
    
    // 노드 3에 연결된 노드 정보 저장
    graph[3].push_back(1);
    graph[3].push_back(7);
    
    // 노드 4에 연결된 노드 정보 저장
    graph[4].push_back(1);
    graph[4].push_back(7);
    
    // 노드 5에 연결된 노드 정보 저장
    graph[5].push_back(2);
    graph[5].push_back(7);
    
    // 노드 6에 연결된 노드 정보 저장
    graph[6].push_back(2);
    graph[6].push_back(7);
    
    // 노드 7에 연결된 노드 정보 저장
    graph[7].push_back(3);
    graph[7].push_back(4);
    graph[7].push_back(5);
    graph[7].push_back(6);
    
   BFS(0);
    return 0;
}

 

DFS와 BFS는 코테에 자주 나오는 유형이라고 하니 확실히 알아두도록 하자!

 

참고 자료 :  Data structures and algorithms in C++ by Michael T. Goodrich, 유튜브 채널 "동빈나" - (이코테 2021 강의 몰아보기) 3. DFS & BFS https://www.youtube.com/watch?v=7C9RgOcvkvo