프로그래머스 - 네트워크(Lv.3)

문제풀이

• 깊이 우선 탐색을 적용하였고, 하나의 시작점을 잡고 탐색이 끝나면 1을 반환한다.
• 네트워크에 속하지 못한 다른 지점을 시작점으로 잡고 위 과정을 반복한다.

구현(All Pass)

#include <string>
#include <vector>

using namespace std;

int link_computer(vector<vector<int>>& computers, vector<bool>& linked, int cur_computer, int n){
    for(int ncom=0; ncom<n; ncom++){
        if(ncom==cur_computer) continue;
        int link_state = computers[cur_computer][ncom];
        if(link_state==1 && linked[ncom]==false){
            linked[ncom]=true;
            link_computer(computers, linked, ncom, n);
        }
    }
    return 1;
}


int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    
    vector<bool> linked(n, false);
    for(int ccom=0; ccom<n; ccom++){
        if(linked[ccom]==true) continue;
        linked[ccom] = true;
        answer += link_computer(computers, linked, ccom, n);
    }
    
    return answer;
}