프로그래머스 - 네트워크(C++)

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

프로그래머스

 

처음 봤을 땐 행렬을 그대로 두고 그래프 순회로 풀 수 있을 것 

이라고 생각해서 백준의 

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

와 같게 풀었다. 그러나 생각을 깊게 하지 않았으니 당연히 테스트 케이스만 맞고 채점 돌리니 무더기로 틀렸다. 하는 수 없이 트리를 구성하여 DFS하였다.

 

1. 벡터로 노드를 구성하고 각 벡터에 인접 노드를 넣는다.

2. DFS

 

유니온 파인드로도 풀 수 있다고 하는데 굳이..?

요즘 그래프 문제는 소홀 했는데 오랜만에 복습할 수 있었다.

 

#include <string>
#include <vector>

using namespace std;

vector<int> network[201];
bool check[201] = {false,};
int N;

void dfs(int here){
    for(int i = 0; i < network[here].size(); i++){
        if(check[network[here][i]] == false){
            check[network[here][i]] = true;
            dfs(network[here][i]);
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    N = n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(i != j && computers[i][j] == 1){
                network[i].push_back(j);
            }
        }
    }

    for(int i = 0; i < n; i++){
        if(check[i] == false){
            answer++;
            dfs(i);
        }
    }
    
    return answer;
}