[백준/JS] 10775 공항

문제 접근

문제링크: https://www.acmicpc.net/problem/10775

10775번: 공항

 

유니온 파인드 문제이다.

알고 풀었는데도 못풀었다. 문제에 그리디가 섞여있는데 그리디 적인 발상을 하지 못했다.

비행기를 해당되는 게이트에 우선적으로 넣고 그 게이트가 차있다면 -1 인 게이트에 넣는다. 라는 그리디적인 발상말이다.

엌엌 🥹

 

문제 풀이

1.  Find 한 비행기의 Root 가 0 이면 break 아니라면 2번을 수행한다.

2. 비행기를 배정되는 게이트, 배정된 게이트 - 1 을 Union 한다.

이런식으로 나가가다 보면 경로 압축에 의해 모두 Root 가 0 을 바라보게 된다.

 

전체 코드

const fs = require("fs");

BOJkey = true;

const input = fs
  .readFileSync(BOJkey ? "./ehddud1006/BOJ/10775/input.txt" : "./dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((item) => item.split(" ").map(Number))
  .reverse();

const [G] = input.pop();
const [P] = input.pop();
const parent = Array.from({ length: G + 1 }, (_, i) => i);
let answer = 0;

for (let i = 0; i < P; i++) {
  const [gi] = input.pop();

  const docking = find(gi);

  if (docking !== 0) {
    merge(docking, docking - 1);
    answer++;
  } else break;
}

function find(u) {
  if (u == parent[u]) {
    return u;
  }
  return (parent[u] = find(parent[u]));
}

function merge(u, v) {
  const U = find(u);
  const V = find(v);
  if (U === V) return;

  parent[U] = V;
}

console.log(answer);

 

시각화된 풀이

말로만 설명하면 이해가 잘 안되어 그림으로 흐름을 알아보자.

입력은 다음과 같다.

4
6
2
2
3
3
4
4

 

1) 2

 

2) 2

 

3) 3

 

4) 3

해당 입력의 경우 3 은 루트 0 을 가르키게 되므로 해당 비행기는 도킹할 수 있는 게이트가 없다.

따라서 답은 3이 된다.

 

시간 복잡도

O(P * log P)