백준17352 - 여러분의 다리가 되어 드리겠습니다 (find-union) node.js

https://www.acmicpc.net/problem/17352

문제는 섬의 갯수 N과 각 섬끼리의 간선들이 주어질 때, '두 섬'을 연결하는 것만으로 모든 섬을 연결할 수 있는 '두 섬'을 찾아 하나만 출력하는 문제다.

 

문제 풀이 방식

집합을 효율적으로 관리하기 위해 find-union 알고리즘을 활용했다. 먼저 주어진 간선들을 사용하여 각 집합을 구분한 뒤, 반복문을 통해 두 섬이 속한 집합이 다른 경우 해당 두 섬 번호를 출력하고 종료시키는 방식으로 로직을 구현했다.

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt")
  .toString()
  .trim()
  .split("\n");

function solution(data) {
  const N = +data.shift();
  
  // 섬 갯수가 2인 경우 1과 2를 연결해주면 끝
  if (N === 2) {
    console.log("1 2");
    return;
  }

  const arr = data.map((el) => el.split(" ").map(Number));

  const roots = {};
  for (let i = 1; i <= N; i++) roots[i] = i;
  
  // find
  function find(x) {
    if (x != roots[x]) roots[x] = find(roots[x]);
    return roots[x];
  }
  
  // union
  function union(a, b) {
    const x = find(a),
      y = find(b);

    if (x == y) return;
    else if (y > x) roots[y] = x;
    else roots[x] = y;
  }

  arr.forEach(([a, b]) => union(a, b));
   
  // 속한 집합이 다른 경우 출력
  for (let i = 1; i <= N; i++) {
    for (let j = i + 1; j <= N; j++) {
      if (find(i) !== find(j)) {
        console.log(`${i} ${j}`);
        return;
      }
    }
  }
}

solution(input);