[백준/JS] 10775 공항

_우지 2023. 5. 2. 22:09

문제 접근

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

10775번: 공항

예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불

www.acmicpc.net

유니온 파인드 문제이다.

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

비행기를 해당되는 게이트에 우선적으로 넣고 그 게이트가 차있다면 -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);