프로그래머스 - 네트워크 - Level 3

문제

풀이전략

1. 네트워크가 몇개인지 찾는 문제이다. 사실상 예전에 백준에서 영역구하기 문제와 비슷하다. 따라서 DFS로 각 Network의 연결을 찾아주고, 서로 연결되지 않은 영역들이 총 몇개인지 찾아주면 된다.

코드

#include <string>
#include <vector>

using namespace std;
// 한번 찾았던 부분을 중복해서 찾지 않기 위한 체크배열
bool ch[201];

void DFS(vector<vector<int> > com, int prev){
    // 연결된 부분의 체크배열은 다 true로 바꾸는 과정
    for(int i=0; i<com[prev].size(); i++){
        if(!ch[i] && com[prev][i] == 1){
            ch[i] = true;
            DFS(com, i);
        }
    }
}
int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    for(int i=0; i<computers.size(); i++){
        if(!ch[i]){
            // DFS를 한번 시작할때마다 네트워크의 개수를 증가. 
            // 결국 한번 DFS를 할때마다 새로운 영역의 네트워크가 생성되는것이기 때문.
            answer++;
            DFS(computers, i);
        }
    }
    return answer;
}

소감

영역구하기 문제와 같은 문제였다. 아마 코딩테스트에서 나오면 훨씬 더 어렵게 나오겠지.... 기본적인 문제이니 정확하게 할줄 알아야한다.