Skip to main content

작성일 : 2024.11.08

네트워크 개수 문제

문제 설명​

컴퓨터들이 네트워크로 연결된 상태가 2차원 배열로 주어질 때, 독립적인 네트워크의 개수를 찾는 문제입니다.

네트워크 연결 특성​

  • 직접 연결: A-B가 연결되어 있음
  • 간접 연결: A-B, B-C가 연결되어 있다면 A-C도 같은 네트워크
  • 모든 연결된 컴퓨터는 하나의 네트워크를 형성

제한 조건​

  1. 컴퓨터 수(n)

    • 범위: 1 ≤ n ≤ 200
    • 컴퓨터 번호: 0 ~ n-1

  2. 연결 정보(computers)

    • computers[i][j] = 1: i번과 j번 컴퓨터가 연결됨
    • computers[i][i] = 1: 항상 1 (자기 자신)

해결 코드​

function solution(n, computers) {
  let answer = 0;
  let visited = new Array(n).fill(0);

  for (let i = 0; i < n; i++) {
    if (visited[i] == 1) continue;
    answer++;
    dfs(computers, visited, i);
  }
  return answer;
}

function dfs(table, visited, node) {
  visited[node] = 1;
  for (let i = 0; i < table.length; i++) {
    if (table[node][i] == 1 && visited[i] == 0) {
      dfs(table, visited, i);
    }
  }
}

알고리즘 설명​

  1. DFS를 사용한 네트워크 탐색

    function dfs(table, visited, node) {
  // 현재 노드 방문 처리
  visited[node] = 1;

  // 연결된 모든 노드 탐색
  for (let i = 0; i < table.length; i++) {
    if (table[node][i] == 1 && visited[i] == 0) {
      dfs(table, visited, i);
    }
  }
}

  2. 네트워크 카운팅

    for (let i = 0; i < n; i++) {
  // 미방문 노드 발견시 새로운 네트워크
  if (visited[i] == 1) continue;
  answer++;
  dfs(computers, visited, i);
}

구현 세부사항​

  1. 방문 배열 초기화
let visited = new Array(n).fill(0);
  1. DFS 탐색 조건
// 연결되어 있고(1) 미방문(0)인 경우만 탐색
if(table[node][i] == 1 && visited[i] == 0)
  1. 네트워크 카운팅 방식
    • 미방문 노드 발견 시 새로운 네트워크로 간주
    • DFS로 연결된 모든 노드 방문 처리
    • 방문하지 않은 다음 노드에서 반복

시간 복잡도​

  • O(n²): 모든 노드에 대해 인접 노드 탐색
  • n은 컴퓨터의 개수

공간 복잡도​

  • O(n): 방문 배열 저장
  • 재귀 호출 스택 사용

예시​

n = 3
computers = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]

결과: 2개의 네트워크
- 네트워크 1: 컴퓨터 0, 1
- 네트워크 2: 컴퓨터 2