[백준20040_자바스크립트(javascript)] - 사이클 게임

🔴 문제

사이클 게임

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [[n, m], ...inputs] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));

const p = Array.from({ length: n }, (_, idx) => idx);

const find = (a) => {
  if (a !== p[a]) p[a] = find(p[a]);

  return p[a];
};

const union = (a, b) => {
  const pA = find(a);
  const pB = find(b);

  if (pA === pB) return true;

  p[pB] = pA;
};

let ans = 0;
for (let i = 0; i < m; i++) {
  const [a, b] = inputs[i];

  if (union(a, b)) {
    ans = i + 1;
    break;
  }
}

console.log(ans);

🟢 풀이

⏰ 소요한 시간 : 15분

유니온 앤 파인드(분리 집합) 유형이다.
처음에 선분을 긋는다... 이래서 공통영역 찾는 문제인 줄 알았는데 단순히 선을 좍좍 그엇을 때 사이클이 언제 형성되는지 찾는 기본 유형이다.
기본 구조인 유니온과 파인드 함수를 구현해주었다. 이 문제는 몇번째에 첫 사이클이 형성되는지 찾는 문제이다. 따라서 유니온연산중 pA와 pB가 처음으로 같아지는 순간이 첫 사이클을 형성하는 순간이므로 이 경우 true를 리턴해 정답을 출력할 수 있도록 한다.

🔵 Ref