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

28 Feb 2023 in Study on Coding Test

그래프 탐색 문제

정답제출코드

#include <string>
#include <vector>

using namespace std;

struct network
{
    vector<int> link;
};

vector<network> networks;
int comVisited[200] = {false};

void dfs(int start)
{
    comVisited[start] = true;
    
    for (int i = 0; i < networks[start].link.size(); ++i)
    {
        int y = networks[start].link[i];
        
        if (!comVisited[y])
            dfs(y);
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    
    for (int i = 0; i < n; ++i)
    {
        network net;
        
        for (int j = 0; j < n; ++j)
        {
            if (j == i)
                continue;
            if (computers[i][j] == 1)
            {
                net.link.push_back(j);
            }
        }
        networks.push_back(net);
    }
    
    for (int i = 0; i < n; ++i)
    {
        if (!comVisited[i])
        {
            dfs(i);
            answer++;
        }
    }
    return answer;
}

DFS를 사용해서 풀었다.

각 구조체를 선언해서 노드마다 연결된 노드 링크를 기록해준다음

for문을 돌려 방문 여부에 따라서 시작점을 결정하고 dfs탐색을 하도록했다.

dfs를 한번 하게 되면 연결된 지점은 모두 탐색되기 때문에 comVisited는 전역변수로 선언했고,

dfs를 돌고나서 다음 comVisited여부가 false인 지점을 만나게 된다면 두번째 네트워크의 시작점이 되는 것이다.