[코딩테스트 C++] 네트워크

오늘의 문제

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

네트워크

나의 풀이

#include <string>
#include <vector>

using namespace std;

bool check[201] = {false, };
void dfs(int in, vector<vector<int>> node){
    if(check[in] == false)
        check[in] = true;
    for(int i=0;i<node[in].size();i++){
        if(check[node[in][i]] == false)
            dfs(node[in][i], node);
    }
}

int solution(int n, vector<vector<int>> computers) { // 컴퓨터 개수, 연결 정보 
    int answer = 0; // 네트워크개수 출력
    
    vector<vector<int>> node(n);
    for(int i=0;i<computers.size();i++){
        for(int j=0;j<computers[i].size();j++){
            if(i != j && computers[i][j] == 1){
                node[i].push_back(j);
            }
        }
    }
    
    for(int i=0;i<n;i++){
        if(check[i] == false){
            dfs(i, node);
            answer++;
        }
    }
    
    return answer;
}

모범 답안

#include <string>
#include <vector>

using namespace std;

void DFS(int from, int n, vector<int> &visited, vector<vector<int>> &computers) {

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

int solution(int n, vector<vector<int>> computers) {

    int network = 0;
    vector<int> visited(n, 0);

    for (int i = 0; i <n; i++) {
        if (visited[i] == 1) {
            continue;
        }

        // visit node and start DFS
        network++;
        visited[i] = 1;

        DFS(i, n, visited, computers);
    }

    return network;
}

배울 점

• 그래프 개수 구하는 문제는 여러번 풀어봐서 호로록 풀었다. 이렇게만 문제나오면 좋을텐데..
• 모든 문제는 쉬운게 없다. 이럴수록 모든 경우에서 고려해보자
• 빨리 푸려고 node 벡터를 만들어 풀었는데 한번 더 생각하면 이게 필요없다. 생각하자 생각.

// 그러면 이렇게 풀이 가능
#include <string>
#include <vector>

using namespace std;

bool check[201] = {false, };
void dfs(int in, vector<vector<int>> node){
    if(check[in] == false)
        check[in] = true;
    for(int i=0;i<node[in].size();i++){
        if( i != in && node[in][i] == 1 && check[i] == false)
            dfs(i, node);
    }
}

int solution(int n, vector<vector<int>> computers) { // 컴퓨터 개수, 연결 정보 
    int answer = 0; // 네트워크개수 출력
    
    for(int i=0;i<n;i++){
        if(check[i] == false){
            dfs(i, computers);
            answer++;
        }
    }
    
    return answer;
}