[백준2162_자바스크립트(javascript)] - 선분 그룹

🔴 문제

선분 그룹

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [[n], ...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);

  p[pb] = pa;
};

const CCW = (x1, y1, x2, y2, x3, y3) => {
  const v1 = [x2 - x1, y2 - y1];
  const v2 = [x3 - x1, y3 - y1];

  const product = v1[0] * v2[1] - v1[1] * v2[0];

  if (product > 0) return 1;
  if (product < 0) return -1;
  return 0;
};

const isCross = ([x1, y1, x2, y2], [x3, y3, x4, y4]) => {
  const ab = CCW(x1, y1, x2, y2, x3, y3) * CCW(x1, y1, x2, y2, x4, y4);
  const cd = CCW(x3, y3, x4, y4, x1, y1) * CCW(x3, y3, x4, y4, x2, y2);

  if (ab === 0 && cd === 0) {
    return (
      Math.min(x1, x2) <= Math.max(x3, x4) &&
      Math.min(x3, x4) <= Math.max(x1, x2) &&
      Math.min(y1, y2) <= Math.max(y3, y4) &&
      Math.min(y3, y4) <= Math.max(y1, y2)
    );
  }

  return ab <= 0 && cd <= 0;
};

for (let i = 0; i < n; i++) {
  for (let j = i + 1; j < n; j++) {
    if (isCross(inputs[i], inputs[j])) union(i, j);
  }
}

const ans = Array(n).fill(0);
for (let i = 0; i < n; i++) {
  ans[find(i)] += 1;
}

console.log(ans.filter((it) => it > 0).length);
console.log(Math.max(...ans));

🟢 풀이

⏰ 소요한 시간 : -

선분이 만나는지 아닌지 확인하기 위해 CCW 선분교차판별 알고리즘을 사용하고,
같은 그룹내에 있는지 아닌지를 확인하기 위해 union-find 알고리즘을 사용한다.

먼저 union-find 알고리즘을 수행하기 위해 총 선분의 개수(n)의 크기를 가진 부모배열 p를 만든다. 그 후 union함수와 find 함수를 각각 정의한다.

다음으로는 총 세 점의 좌표정보를 매개변수로 받아 CCW 알고리즘을 수행하는 함수를 정의한다. 벡터의 외적을 이용해 세 점이 시계방향을 이루는지, 반시계방향을 이루는지, 일직선 내에 있는지를 리턴한다.

그 후 isCross 함수를 정의해 네개의 점을 기준으로 해당 선분이 서로 만나는지 아닌지를 리턴한다. 중요한점은 문제에서 끝점을 지나 스치는 경우도 만나는 경우로 포함한다 했으므로, 세 점이 일직선일 경우에 각각의 점이 만나고 있는지 아닌지를 따로 고려해주면 된다.

구현에 필요한 함수들이 다 정의 됐으므로 모든 점들을 순회하면서 isCross함수를 통해 겹치는지 확인하고, 겹친다면 union 연산을 해주면 된다.

마지막으로 모든 선분에 대해 find 연산을 수행해 부모를 찾아준 뒤 개수를 세어주면 된다.

🔵 Ref