그래프 탐색 문제 (SV2 연결 요소의 개수)

문제

11724 연결 요소의 개수
https://www.acmicpc.net/problem/11724
알고리즘 분류: 그래프 탐색, DFS, BFS

풀이

이 문제 삽질을 많이 했다. 왜냐하면 문제의 내용을 정확히 파악하지 못했다.

입력값

6 2
3 4
4 2

입력값이 위와 같을 때 그래프는 위 그림처럼 표현할 수 있다.

이 때, 주의할 것이 두가지가 있다.

• 간선이 무방향인 그래프이다.
• 연결 요소의 개수를 구할 때 2-4-3 처럼 간선으로 이루어진 그래프 뿐만 아니라 1, 5, 6 간선도 연결 요소이다.
  즉, 위 그래프의 연결 요소의 개수는 1이 아닌 4이다.

구현 코드

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";

const [[N, M], ...arr] = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n")
  .map((i) => i.split(" ").map(Number));

// 각 노드가 연결된 정보를 배열로 표현 (2차원 배열)
const graph = Array.from({ length: N + 1 }, () => []);
for (let i = 0; i < M; i++) {
  // 무방향 그래프 특징을 감안하여 배열을 표현한다.
  graph[arr[i][1]].push(arr[i][0]);
  graph[arr[i][0]].push(arr[i][1]);
}

// 각 노드가 방문된 정보를 배열로 표현 (방문한것은 1, 그렇지 않은 것은 0)
const visited = Array.from({ length: N + 1 }, () => 0);

// DFS 함수
function dfs(graph, start, visited) {
  // 현재 노드 방문처리
  visited[start] = 1;
  for (const i of graph[start]) {
    // 현재 노드와 연결된 다른 노드 재귀적으로 방문
    if (!visited[i]) dfs(graph, i, visited);
  }
  // 간선이 서로 연결된 노드를 모두 검사했으면 1을 반환
  return 1;
}

function solution(M, arr) {
  let result = 0;

  // 간선이 없는 경우 노드의 개수가 연결 요소 개수
  if (M === 0) return N;

  for (let i = 0; i < M; i++) {
    // 노드가 방문된 상태가 아니면 DFS 함수 호출
    if (visited[arr[i][0]] === 0) {
      result += dfs(graph, arr[i][0], visited);
    }
  }
  // 연결된 노드 없이 홀로 있는 노드의 수
  const alone = visited.filter((i) => i === 0).length - 1;
  return result + alone;
}

const answer = solution(M, arr);
console.log(answer);

Today I Learned

JS 문법

빈 배열 5개 요소를 가지는 배열을 생성할 때,
Array.from() 과 new Array().fill() 차이

const array = Array.from({ length: 5 }, () => []);

const array = new Array(5).fill([]);

위 두 문장 모두 array을 출력하면 [ [], [], [], [], [] ] 같은 출력값이 나온다.

그러나,

array[0].push(1);

위 코드를 실행한다면
Array.from() 로 선언한 배열의 출력값은 다음과 같고,

[ [ 1 ], [ 0 ], [ 0 ], [ 0 ], [ 0 ] ]

new Array().fill() 로 선언한 배열의 출력값은 다음과 같다.

[ [ 1 ], [ 1 ], [ 1 ], [ 1 ], [ 1 ] ]

왜 이런 원치 않는 동작이 일어나는 것일까?

• new Array()로 생성된 배열은 실제로 빈 배열을 가리키는 참조를 가지고 있다. fill([]) 메소드는 주어진 배열([])을 참조하여 해당 배열로 모든 요소를 채우는 것이 아니라, 배열이 가리키고 있는 참조를 공유하는 것이다.
• 따라서 fill([])로 요소를 채우면, 모든 요소가 동일한 빈 배열을 참조하게 된다.

이로 인해 하나의 요소를 수정하면 다른 요소에도 동일한 변경이 반영된다.

💡 따라서 배열을 생성할 때는 각 요소가 독립적인 빈 배열을 가지도록 하기 위해 다른 방법을 사용해야 한다.
Array.from()을 사용하면 각 요소가 서로 다른 빈 배열을 가지게 된다.