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

한문제만 풀기 섭섭해서 한 문제 더 풀었다.

원래는 DP에 있는 N으로 표현 문제를 풀다가 너무 어려워서 이 문제로 도망쳤는데

오히려 아까 푼 문제보다 더 빨리 푼 듯하다. 푸는데 5분 정도 걸린거 같다.

레벨3 치고는 너무 쉽거나 내가 DP를 겁나 못하거나 둘 중 하나겠지.

 

처음엔 union-find로 풀까 하다가 단순히 DFS만 돌려도 될 것 같길래 이렇게 풀었다.

어느 한 노드에서 DFS를 시작해서 끝났는데도 아직 방문하지 않은 노드는 다른 네트워크다.

따라서 모든 노드를 방문할 때까지 DFS를 돌리면 그 횟수가 네트워크의 개수가 된다.

 

#include <string>
#include <vector>

using namespace std;

int visit[201] = { 0, };

void DFS(int cur, int n, vector<vector<int>> computers){
    visit[cur] = 1;
    
    for(int i = 0; i < n; i++){
        if(computers[cur][i] == 1 && visit[i] == 0)
            DFS(i, n, computers);
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    
    for(int i = 0; i < n; i++){
        if(visit[i] == 0){
            answer++;
            DFS(i, n, computers);
        }
    }
    
    return answer;
}

 

후기)

너무 쉽게 풀어서 맛없다.

한문제 더 풀어야지.