[프로그래머스] 네트워크

문제

 

 

분석

친절하게 제목에 dfs/bfs 라고 쓰여있다. 

탐색으로 문제를 풀면 될것 같다.

 

1 - 2 - 3 노드 가 연결 되어 있다고 하자.

그렇다면 1번 방문, 2번 방문, 3번 방문 하면서 방문을 하면 0 으로 만들어 주고 

또 방문 하지 않도록 한다.

 

그렇 한번 순회를 할때마다 1씩 카운터를 올려 주면 총 노드의 집합이 몇개 인지 구 할수 있다.

 

 

 

코드

#include <string>
#include <vector>

using namespace std;


bool solve(int node, vector<vector<int>> &computers) 
{
    if (!computers[node][node]) {
        return false;
    }
    
    computers[node][node] = 0;
        
    for (int i = 0; i < computers.size(); i++ ) {
        if (computers[node][i]) {
            solve(i, computers);
        }
    }
    
    return true;
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    for(int i = 0; i < n; i++) {
        if(computers[i][i] && solve(i, computers)) {
            answer++;
        }
    }
    return answer;
}

 

 

 

결과