프로그래머스(깊이/너비 우선 탐색; 네트워크) c++

#include <string>
#include <vector>

using namespace std;

vector<bool> bvisited;

void dfs(int n, vector<vector<int>> computers, int count)
{
    bvisited[count] = true;   // 현재 컴퓨터 방문 처리
    
    for(int next = 0; next < n; ++next)
    {
        // count과 next가 연결되어 있고, 아직 안 가봤으면
        if(computers[count][next] == 1 && !bvisited[next])
        {
            dfs(n, computers, next);
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    bvisited.assign(n, false);
    
    for(int i = 0; i < n; ++i)
    {
        if(!bvisited[i])          // 아직 어떤 네트워크에도 안 속한 컴퓨터라면
        {
            dfs(n, computers, i);
            answer++;              // 새 네트워크 하나 발견
        }
    }
    return answer;
}

 

해설:

 

각 컴퓨터들이 존재하며 각 네트워크들이 전부 연결 되어있다면 네트워크는 1개로 본다. 예를 들어 3개의 컴퓨터중 2개는 연결 되어있고 다른 하나의 컴퓨터는 연결이 안되있다고 하면 네트워크는 두개이다.

 

첫번째: bvisited의 불리언형 배열을 선언하여 방문한적이 있다고 하면은 하나의 네트워크로 간주한다.

두번째: 먼저 assign을 통해 배열의 크기를 정해준다. 그 다음 반복문을 통해 크기만큼 반복을 실행해주며 방문한적 없는 경우 dfs를 실행한다(맨 처음의 경우 어떠한 컴퓨터에도 방문한적 없기때문에 무조건 실행된다).

세번쨰: dfs를 실행하며 방문을 했다는 것을 남기기 위해 bvisited를 true로 변경하며 컴퓨터의 수만큼 반복하여 computers[count][next] == 1 활성화 되어있거나 !bvisited[next] 방문한적이 없으면 그 다음으로 방문하여 count->next 인덱싱으로 넘어가면 연결 되어있는 모든 컴퓨터에 방문한다.

네번째; 다시 solution으로 돌아와 answer(네트워크 수)를 증가 시키면 다시 반복을 돌아 방문한적이 없다면 다시 answer를 증가 시켜 네트워크 수를 증가 시킨다.