[백준1976_자바스크립트(javascript)] - 여행 가자

🔴 문제

여행 가자

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const inputs = fs.readFileSync(path).toString().trim().split('\n');
const n = Number(inputs[0]);
const plans = inputs[inputs.length - 1].split(' ').map(Number);
const p = Array.from({ length: n }).map((_, idx) => idx);

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

  return p[a];
};

const union = (i, j) => {
  const pI = find(i);
  const pJ = find(j);

  p[pJ] = pI;
};

for (let i = 2; i < inputs.length - 1; i++) {
  const input = inputs[i].split(' ').map(Number);
  for (let j = 0; j < n; j++) {
    if (input[j] && i - 2 < j) {
      union(i - 2, j);
    }
  }
}

let ans = [];

for (const plan of plans) {
  ans.push(find(plan - 1));
}

const set = new Set(ans);
console.log(set.size === 1 ? 'YES' : 'NO');

🟢 풀이

⏰ 소요한 시간 : 30분

유니온 & 파인드로 문제를 풀이했다.
도시의 개수 n을 입력받아 대표값 배열 p를 만들어 줬다.
입력의 가장 마지막 줄의 경우 여행 계획이므로 plans이라는 배열로 분리했고 나머지 inputs을 순회하며 union 연산을 해주면 된다.
이때 n x n 형태로 연결되었는지 아닌지를 1과 0으로 구분해서 주어진다. 따라서 해당 위치 input[j]가 1일때만 즉 연결되어 있을 경우에만 union 연산을 진행한다. 이 때 연결에는 방향이 없으므로, i-2와 j가 연결된 것과 j와 i-2가 연결된 것은 동일하다. 따라서 두 번 연산할 필요 없이 i-2가 j보다 더 작은 경우에만 union 연산을 진행한다.
union 함수는 i와 j 의 대표를 찾아 j의 대표를 i로 갱신해 주는 방식으로 구현했다.
find 함수는 a가 p[a]와 다를 경우 재귀호출을 하여 대표값을 찾아준다.

마지막 여행계획에 들어있는 도시들이 같은 대표를 가지고 있는지 확인하면 되므로 find 연산한 값을 모두 ans 에 담아 set으로 변환하여 길이로 정답을 구분해 출력한다.

🔵 Ref