[프로그래머스 / Level 3] 네트워크 (C++)

https://programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

DFS를 이용하면 풀 수 있는 문제입니다.

 

문제 접근법

• 컴퓨터 방문 여부 체크를 위한 bool 배열을 선언한다.
• 0번 컴퓨터 부터 n - 1번 컴퓨터 까지 연결된 컴퓨터 방문 여부 체크 함수를 시행한다(단, 해당 컴퓨터의 bool 배열이 방문하지 않음으로 체크되어 있는 컴퓨터만 시행한다).
• 해당 함수가 시행된 횟수가 네트워크의 갯수와 같다.

아래는 코드입니다.

#include <string>
#include <vector>
 
using namespace std;
 
vector<vector<int>> com;
bool check[201];
 
void DFS(int n, int index)
{
    check[index] = true;
    
    for(int i = 0; i < n; i++)
    {
        if(!check[i] && com[index][i])
            DFS(n, i);
    }
    
    return;
}
 
int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    com = computers;
    
    for(int i = 0; i < n; i++)
    {
        if(!check[i])
        {
            answer++;
            DFS(n, i);
        }
    }
    
    return answer;
}