[PCCP] Lv3: 네트워크(43162) 해설

문제

- 문제 링크: 네트워크

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

- N: 노드(컴퓨터)의 개수

- E: 간선의 개수

- 인접행렬로 구현한 깊이우선탐색은 노드의 연결 여부에 상관없이 모두 체크하므로 시간 복잡도는 O(N^2)

- computers의 정보가 인접행렬이므로 O(N^2)

#include <string>
#include <vector>

using namespace std;

vector<bool> visited;

// 깊이우선탐색을 수행하는 함수
void dfs(const vector<vector<int>>& network, int node) {
    visited[node] = true;
    
    for (int i = 0; i < network[node].size(); ++i) {
        if (network[node][i] && !visited[i]) {
            dfs(network, i);
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    visited = vector<bool>(computers.size(), false);
    
    int networkCount = 0;
    
    // 네트워크의 수를 확인
    for (int i = 0; i < computers.size(); ++i) {
        if (!visited[i]) {
            dfs(computers, i);
            networkCount++;
        }
    }
    return networkCount;
}

solution 2) 상호배타적 집합 활용

- 각 네트워크를 집합으로 표현하고 개수를 셈

#include <vector>
#include <unordered_map>

using namespace std;

int parent[201];

// 노드의 루트를 찾는 함수
int findParent(int node) {
    if (node == parent[node])
        return node;
    return parent[node] = findParent(parent[node]);
}

// 두 노드를 연결하는 함수
void unionNodes(int node1, int node2) {
    int root1 = findParent(node1);
    int root2 = findParent(node2);
    if (root1 != root2) {
        parent[root2] = root1;
    }
}

// 네트워크 개수를 계산하는 함수
int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    for (int i = 0; i < n; ++i) {
        parent[i] = i; // 각 노드의 부모를 자기 자신으로 초기화
    }
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (computers[i][j]) {
                unionNodes(i, j); // 연결된 컴퓨터들을 그룹화
            }
        }
    }
    
    unordered_map<int, bool> networkFound;
    for (int i = 0; i < n; ++i) {
        int root = findParent(i); // 각 노드의 루트 노드 찾기
        if (!networkFound[root]) { // 새로운 네트워크 발견시 카운트 증가
            answer++;
            networkFound[root] = true;
        }
    }
    return answer;
}

solution 3)

#include <string>
#include <vector>

using namespace std;

int check[200]; 

void dfs(int current_computer, int n, vector< vector<int> > computers) { 
  check[current_computer] = 1;

  for(int i=0; i<n; i++) { 
    if(check[i] == 0 && computers[current_computer][i] == 1) {   
      dfs(i, n, computers); 
    } 
  } 
} 

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

  for(int i=0; i<n; i++) { 
    if(check[i] == 0) { 
      dfs(i, n, computers);
      answer++; 
    } 
  } 
  return answer;
}

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1) X 수정 필요 에러

- N: 노드(컴퓨터)의 개수

- E: 간선

- 인접행렬로 구현한 깊이우선탐색은 노드의 연결 여부에 상관없이 모두 체크하므로 시간 복잡도는 O(N^2)

- N이 최대 200이므로 시간 복잡도는 무관

class Solution {
    private static boolean[] visit;
    private static int[][] computer;
    
    private static void dfs(int now) {
        visit[now] = true; // 현재 노드 방문 처리
        for (int i = 0; i < computer[now].length; ++i) {
            // 연결되어 있으며 방문하지 않은 노드라면
            if (computer[now][i] == 1 && !visit[now]) {
                dfs(i); // 해당 노드를 방문하러 이동
            }
        }
    }
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        computer = computers;
        visit = new boolean[n]; // 방문 여부를 저장할 배열
        
        for (int i = 0; i < n; ++i) {
            if (!visit[i]) { // 아직 방문하지 않은 노드라면 해당 노드를 시작으로 깊이 우선 탐색 진행
                dfs(i);
                answer++; // DFS로 연결된 노드들을 모두 방문하면서 네트워크 개수 증가
            }
        }
        
        return answer;
    }

}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: 노드(컴퓨터)의 개수

- E: 간선

- 인접행렬로 구현한 깊이 우선 탐색은 노드의 연결 여부에 상관없이 모두 체크하므로 시간 복잡도는 O(N^2)

- N이 최대 200이므로 사실 시간 복잡도는 무관

def dfs(computers, visited, node):
    visited[node] = True # 현재 노드 방문 처리
    for idx, connected in enumerate(computers[node]):
        if connected and not visited[idx]: # 연결되어 있으며 방문하지 않은 노드라면
            dfs(computers, visited, idx) # 해당 노드를 방문하러 이동
            
def solution(n, computers):
    answer = 0
    visited = [False] * n # 방문 여부를 저장하는 리스트
    for i in range(n):
        if not visited[i]: # 아직 방문하지 않은 노드라면 해당 노드를 시작으로 깊이 우선 탐색 진행
            dfs(computers, visited, i)
            answer += 1 # DFS로 연결된 노드들을 모두 방문하면서 네트워크 개수 증가
    return answer

solution 2)

check = [0 for i in range(200)]

def dfs(graph, cur, n):
    check[cur] = 1
    for i in range(n):
        if check[i] == 0 and graph[cur][i] == 1:
                dfs(graph, i, n)
    return

def solution(n, computers):
    answer = 0
    for i in range(n):
        if check[i] == 0:
            dfs(computers, i, n)
            answer += 1
    return answer

solution 3)

import

 

(JavaScript)

solution 1)

- N: 노드(컴퓨터)의 개수

- E: 간선의 개수

- 인접행렬로 구현한 깊이 우선 탐색은 노드의 연결여부에 상관없이 모두 체크: O(N^2)

- N이 최대 200이므로 시간복잡도는 무관

function dfs(computers, visited, node) {
    visited[node] = true; // 현재 노드 방문 처리
    
    for (let idx = 0; idx < computers[node].length; ++idx) {
        if (computers[node][idx] && !visited[idx]) { // 연결되어 있으며 방문하지 않은 노드라면
            dfs(computers, visited, idx); // 해당 노드를 방문하러 이동
        }
    }
}

function solution(n, computers) {
    let answer = 0;
    const visited = Array(n).fill(false); // 방문 여부를 저장하는 배열
    
    for (let i = 0; i < n; ++i) {
        if (!visited[i]) { // 아직 방문하지 않은 노드라면
            dfs(computers, visited, i); // DFS로 연결된 노드들을 모두 방문하면서 네트워크 개수 증가
            answer++;
        }
    }
    return answer;
}

solution 2)

import

solution 3)

import