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

네트워크

문제 링크

네트워크

분석

n은 컴퓨터의 개수를 가리킵니다.
각 컴퓨터는 0부터 n - 1로 0-based입니다.

computers는 n x n크기의 2차원 배열입니다.
computers[i][j]가 1이면 i번 컴퓨터와 j번 컴퓨터가 직접 연결되어 있음을 의미합니다.

무방향 그래프에서 네트워크의 개수를 세어 반환하면 됩니다.
개수를 셀 때 DFS나 BFS를 사용할 수 있습니다.
이때, 방문 처리를 해주어야 합니다.

풀이

#include <vector>

using namespace std;

// 현재 노드를 방문 처리하고, 연결된 노드 중 방문하지 않은 노드를 재귀적으로 방문한다.
void dfs(vector<vector<int>>& computers, vector<bool>& visited, int n, int node)
{
    visited[node] = true;
    
    for (int i = 0; i < n; ++i)
    {
        if (computers[node][i] == 1 && !visited[i])
        {
            dfs(computers, visited, n, i);
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    
    // 방문에 대한 정보를 저장하는 배열
    vector<bool> visited(n, false);
    
    // 모든 노드를 순회하며, 방문하지 않았던 노드를 재귀적으로 방문한다.
    for (int i = 0; i < n; ++i)
    {
        if (!visited[i])
        {
            dfs(computers, visited, n, i);
            ++answer;
        }
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n^2)$입니다.

• 각 노드에 대해 DFS 수행 $O(n^2)$
  • DFS에서 n개의 노드를 방문 할 수 있다.

공간 복잡도는 $O(n)$입니다.

• 방문에 대한 정보를 저장하는 배열 vector<bool> visited $O(n)$
• DFS의 재귀 호출 스택 $O(n)$
• $O(n) + O(n)$

테스트 성능

테스트 1 〉 통과 (0.01ms, 4.21MB)
테스트 2 〉 통과 (0.01ms, 4.2MB)
테스트 3 〉 통과 (0.01ms, 4.18MB)
테스트 4 〉 통과 (0.01ms, 4.01MB)
테스트 5 〉 통과 (0.01ms, 4.19MB)
테스트 6 〉 통과 (0.03ms, 4.2MB)
테스트 7 〉 통과 (0.01ms, 4.13MB)
테스트 8 〉 통과 (0.02ms, 4.18MB)
테스트 9 〉 통과 (0.02ms, 4.45MB)
테스트 10 〉 통과 (0.01ms, 4.22MB)
테스트 11 〉 통과 (0.05ms, 4.13MB)
테스트 12 〉 통과 (0.04ms, 4.19MB)
테스트 13 〉 통과 (0.03ms, 3.89MB)