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

문제 링크

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

프로그래머스

 

 

코드 구현

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// 모든 컴퓨터가 간접적으로 연결되어 있으면 하나의 네트워크
// dfs 로 방문체크 하면서 순환 -> dfs 횟수 = 네트워크 개수

bool visited[200];
int answer = 0;

void dfs(const vector<vector<int>>& computers, int startNode)
{
    if (visited[startNode] == true) return;

    visited[startNode] = true;

    for (int i = 0; i < computers.size(); i++)
    {
        if (computers[startNode][i])
        {
            dfs(computers, i);
        }
    }
}

int solution(int n, vector<vector<int>> computers) 
{
    for (int i = 0; i < n; i++)
    {
        if (!visited[i])
        {
            dfs(computers, i);
            answer++;
        }
    }

    return answer;
}

 

 

해결 방법

dfs를 이용하여 해결하였다. 0번 컴퓨터부터 순회를 시작하여 연결되어있는 모든 컴퓨터를 깊이 우선 탐색으로 순회하고, 방문한 컴퓨터들을 방문 체크 한다. 순회 한 번이 끝나면 네트워크 개수를 하나 추가한다. 연결 되어 있지 않은 컴퓨터가 있으면 방문 체크가 되어있지 않은 컴퓨터부터 다시 순회를 시작하고 순회가 끝나면 네트워크 개수를 추가한다.