백준20040 - 사이클 게임 (스패닝 트리) node.js

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

해당 문제는 첫줄에는 점의 갯수 n과 연결된 선분의 갯수 m, 그리고 다음 줄부터 게임의 진행 상황이 주어진다. 게임의 진행 상황은 a점, b점이 연결되었음을 말하며, 만약 사이클이 완성된 경우 완성된 진행상황의 순번을 출력, 사이클이 완성되지 않은 경우 0을 출력하면 된다.

 

문제 풀이 방식

사이클에 힌트를 얻어 최소 스패닝 트리 문제에서 사용하던 find-union 알고리즘을 활용했다. 게임 진행 상황에 따라 a점과 b점을 병합(union)하되, 병합하기 전 각각의 a,b가 같은 루트 노드를 가지고 있을 경우(find) 현재 진행 순번을 출력하고 마무리하는 방식으로 구현했다.

전체 소스 코드

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

function solution(data) {
  const [[n, m], ...edges] = data.map((el) => el.split(" ").map(Number));

  const roots = {};
  for (let i = 1; i <= n; i++) roots[i] = i;

  function find(node) {
    if (roots[node] != node) roots[node] = find(roots[node]);
    return roots[node];
  }

  function union(a, b) {
    const rootA = find(a),
      rootB = find(b);

    if (rootA < rootB) roots[rootB] = rootA;
    else roots[rootA] = rootB;
  }

  for (let i = 0; i < m; i++) {
    const [s, e] = edges[i];
    if (find(s) == find(e)) {
      console.log(i + 1);
      return;
    }
    union(s, e);
  }
  console.log(0);
}

solution(input);