[Lv.3] 네트워크

출처. 프로그래머스

프로그래머스

 

컴퓨터 갯수가 주어지고, 연결 정보가 주어진다.

주어진 정보로 총 몇개의 네트워크가 구성되는지 구하는 문제이다.

이 문제는 단순히 DFS로 풀면 간단하다. 이미 한번 방문했는지 저장하는 변수를 두고, 각 노드에서 연결된 모든 노드들을 반복해서 방문하면 된다. DFS & 재귀로 풀면 된다.

 

내용은 주석 참고

#include <vector>

#define MAX     (200U)

using namespace std;

bool visited[MAX];

void DoVisit(size_t cur, int n, vector<vector<int>>& computers) {
    visited[cur] = true; // 현재위치를 방문체크
    
    for (size_t i = 0 ; i < n ; i++) {
        if (!visited[i] && computers[cur][i] == 1) // 0~n 까지 반복하면서 방문안했고, 나랑 연결됬는지 조건검사를 통해 또 방문하도록 함
            DoVisit(i, n, computers);        
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    
    for (size_t idx = 0 ; idx < n ; idx++) {
        if (!visited[idx]) { // 방문했는지 체크
            DoVisit(idx, n, computers); // 방문안했으면, 현재 위치노드를 방문한다
            answer++; // 한번 다 돌았으면 하나의 네트워크로 구성됨
        }
    }
    
    return answer;
}