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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

네트워크가 몇 개의 그룹으로 구성되어있는지 확인하는 문제이다. 방문 여부를 체크하는 배열을 만들고 DFS탐색을 하면 같은 네트워크에 속한 컴퓨터들은 재귀적으로 DFS 탐색을 하기 때문에 solution 함수에서 DFS를 총 몇 번 수행하는지를 세어주면 된다.

코드

#include <string>
#include <vector>

using namespace std;

void dfs(int n, vector<vector<int>>& computers, vector<bool>& visited, int idx){
    visited[idx] = true;

    for(int i=0; i<n; i++){
        if(!visited[i] && computers[idx][i])
            dfs(n, computers, visited, i);
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    vector<bool> visited(n, false);
    for(int i=0; i<n; i++)
        if(!visited[i]){
            answer++;
            dfs(n, computers, visited, i);
        }
    return answer;
}