코딩테스트: 깊이/너비 우선 탐색(DFS/BFS)를 풀어보자!

https://school.programmers.co.kr/learn/courses/30/lessons/17687

프로그래머스

문제는 바로 위에 있으니, 혹시 안 풀어본 분들이라면 풀어보시길 바란다.

Lv.3 문제이나, DFS나 BFS에 대한 개념을 가지고 있다면, 접근이 가능하며..

필자는 이진트리 개념으로만 알고 있었기 때문에, 챗GPT의 힘을 빌려 풀긴 했다.

다만, 이 개념에 대해 어떻게 접근하였는지, 또 어떻게 이해가 가능한지 설명하기 위해 풀이법을 기술해 보고자 한다.

 

DFS와 BFS

알고리즘 문제를 푸는 사람이라면 어느 정도 단계가 올라간 이후로는 이 탐색법에 대해 꼭 들어보았을 것이다.

단순히 들어보는 것 뿐만 아니라, 실제로 문제를 풀 때에도 이는 자주 활용이 된다.

이 두 가지 방법에 대해 자세히는 설명을 하기 보다는 요약을 하고자 하며(혹시나 모르시는 분이 있다면 추가 조사를 부탁드린다),

이후 이 탐색법에 특징을 어떻게 문제에 적용시킬 수 있는 지 알아보고자 한다.

 

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

BFS(Breadth First Search), 넓이 우선 탐색

알고리즘 문제를 푸는 사람이라면 어느 정도 단계가 올라간 이후로는 이 탐색법에 대해 꼭 들어보았을 것이다.

자료 구조 중에서는 node라고 하여 하나의 점이 되는 데이터와

이 node라는 점들을 연결을 시켜주는 edges 즉, 선분이 되는 데이터로 이루어진 것이 있다.

위에 사진은 node와 edges로 이루어진 Tree(나무)라는 자료구조인데,

상위에는 부모 node가 존재하며, 아래로는 자식 node가 마치 나무의 가지처럼 뻗쳐나가는 자료 구조이다.

 

이러한 Tree 구조를 훑어보는 방식이 대략 두 가지로 나눠지며, 대표적인 것이: 깊이 우선 탐색, 넓이 우선 탐색이다.

깊이 우선 탐색(DFS)은 말 그대로, 좌측 부터 시작하여 자식 노드 우선으로 탐색을 한다.

깊이 내려가서 이제 더 이상 자식노드가 없을 경우, 위로 올라가, 가서 우측의 다음 자식노드를 탐색한다.

넓이 우선 탐색은 자식 노드를 우선으로 탐색하는 것이 아닌 같이 연결되어 있는, 동일한 깊이(depth)인 노드를 우선으로 탐색한다.

따라서, 맨 부모 노드 다음 1세대(?) 자식 노드를 탐색하고, 끝난 다음에는 2세대 자식 노드를 탐색하는 식이다.

출처: http://blog.hackerearth.com/wp-content/uploads/2015/05/dfsbfs_animation_final.gif

이해를 위해 git 파일을 추가하였다.

 

하지만, 여기서 문제가 있다. 이러한 트리 구조라면 모를까,

문제에서 나오는 것은 서로 간에 연결된 일종의 graph이다.

그리고, 이 그래프의 node들이 연결되어 있는 하나의 뭉치를 한 개의 network로 치고,

각각 별 개로 떨어진, network의 갯수를 구하는 문제이다.

 

하지만, DFS의 작동방식을 파악하면 생각보다 간.단.한 문제가 될 수 있다.

Lv.3 짜리 문제지만, 생각보다 핵심 개념이 들어있고, 푼 사람 숫자가 꽤 많은 것도 이를 증명한다고 본다.

 

 

그래프(Graph)로 본 DFS 탐색 방식

먼저, 그래프일 경우, DFS는 어떻게 탐색을 할까? 아래 그림을 살펴보자.

출처: https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

그래프의 경우, 상호간의 연결이 이루어져 있기 때문에,

트리 자료 구조 처럼 무조건 depth(깊이)가 아래인 곳으로 탐색을 하게 되면,

무한으로 순환하는 구조가 되어버린다.

 

따라서, 그래프의 경우, 이미 특정 노드를 방문을 하였다는 표식을 별도로 해야 할 필요가 있다.

위 그림에서 (4)에서 이미 모든 노드를 방문하였다. 

단계 (5)에서 4번 노드와 연결된 다른 노드를 탐색을 하려고 하지만,

이미 0, 3, 2번 노드는 방문을 하였기 때문에 다른 노드로 탐색 위치가 옮겨지지 않는다.

 

또한, 이러한 DFS 탐색은 기본적으로 재귀 함수(모르시는 분이 계시다면 알아보시길 부탁드린다)로 이루어지기 때문에,

4번 노드에서 탐색이 끝나면 바로 위 depth인 3번 노드 > 2번 노드 > 1번 노드 이런 식으로 벗겨(?)지게 된다.

 

 

자, 그럼 여기서 문제의 핵심이 나온다.

해당 문제에서는 네트워크가 서로 독립되어 있는 갯수를 구하는 것이다.

만약 예시를 그리자면, 위의 그림과 같이 좌-우 두 개의 네트워크가 존재한다.

이 뜻은, 위의 그림과 다르게, 시작점 하나 만으로 모든 정점을 순회하는 것이 불가능하다는 것이다.

즉, 0 - 1 - 2 - 3 - 4 로 순회를 하면서, 방문한 노드를 모두 표식을 하더라도,

5번과 6번은 표식이 되어 있지 않을 뿐더러 별도로 순회를 해야 한다.

따라서 별도로 순회를 한 횟수 = 네트워크의 총 갯수 라는 말이 성립이 된다.

 

 

코드를 짜자면 이런 방법을 생각하면 된다.

1. 0번 노드부터 6번 노드까지 모두 순회 할 수 있는 반복문을 만든다.

2. 반복문 안에는 시작 노드를 인자값으로 받는 dfs 함수를 넣는다 & dfs 함수는 방문한 노드는 재방문을 못하도록 막아놓는다.

3. 반복문이 돌아간다. dfs가 돌아가면서, 먼저 0-1-2-3-4 가 돌아가면서 모두 방문한 노드로 표식이 된다. 여기서 네트워크가 한개 카운트 된다.

4. 반복문이 돌아간다. 1번, 2번, 3번, 4번을 시작으로 인자값을 박는 dfs 함수는 이미 재방문 하였으므로 dfs가 돌아가지 못한다.

5. 반복문이 돌아간다. 5번을 시작으로 하는 dfs 함수는 재방문하지 않았으므로 dfs가 돌아간다 (5-6 노드방문). 여기서 네트워크가 추가로 카운트 된다.

6. 반복문이 돌아간다. 6번은 방문하였으므로 dfs가 돌아가지 않는다.

 

이렇게 해서 총 2개의 네트워크가 카운트 된다!

코드는 아래와 같다:

function solution(n, computers) {
    let networkCount = 0;
    const visited = new Array(computers.length).fill(false);
    
    for(let i = 0; i <computers.length; i++){
        if(!visited[i]){
            dfs(computers[i], i, visited);
            networkCount++;
        }
    }
    
    function dfs(connectedList, rootComputer, visited){
        visited[rootComputer] = true;
        for(let i = 0; i < connectedList.length; i++){
            if(computers[rootComputer][i] === 1 && !visited[i]){
                dfs(computers[i], i, visited);
            }
        }
    }
    
    
    var answer = networkCount;
    return answer;
}