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

문제

---

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

풀이

---

DFS로 주어진 연결 정보를 통해 네트워크의 개수를 구하는 문제로, 네트워크는 컴퓨터간 연결요소가 존재 시, 1개의 네트워크로 친다. 따라서 아무하고도 연결되어있지 않거나, 각각 다른 컴퓨터끼리 연결되어 있는 경우를 탐색한다. 따라서 각 컴퓨터의 연결 요소를 저장하고, 순차적으로 연결 요소가 존재하나, 방문하지 않은 경우를 탐색하여 1개의 네트워크를 생성한다. 이후 방문하지 않은 컴퓨터는 연결 요소 유무에 따라 DFS를 진행하여 네트워크 개수를 업데이트한다.

#include <string>
#include <vector>
#include <map>

using namespace std;

bool isVisited[201] = { false };
vector<vector<int>> connects(201);

void DFS(vector<int> connect, int idx)
{
    if (isVisited[idx] == true)
    {
        return;
    }

    else
    {
        isVisited[idx] = true;
    }

    for (int i = 0; i < connect.size(); i++)
    {
        DFS(connects[connect[i]], connect[i]);
    }
}

int solution(int n, vector<vector<int>> computers)
{
    int answer = 0;

    for (int i = 0; i < computers.size(); i++)
    {
        for (int j = 0; j < computers[i].size(); j++)
        {
            if (i != j && computers[i][j] == 1)
            {
                connects[i + 1].push_back(j + 1);
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if (isVisited[i] == false)
        {
            DFS(connects[i], i);
            answer++;
        }
    }


    return answer;
}