IT/알고리즘

[BAEKJOON] 백준 4803번: 트리 (node.js)

무녈 2023. 1. 8. 14:47

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

 

4803번: 트리

입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다.

www.acmicpc.net

 

문제

그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.

트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해서 경로가 유일하다.

그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n ≤ 500과 m ≤ n(n-1)/2을 만족하는 정점의 개수 n과 간선의 개수 m이 주어진다. 다음 m개의 줄에는 간선을 나타내는 두 개의 정수가 주어진다. 같은 간선은 여러 번 주어지지 않는다. 정점은 1번부터 n번까지 번호가 매겨져 있다. 입력의 마지막 줄에는 0이 두 개 주어진다.

출력

입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다.

풀이

입력 받은 값대로 순회하며 유니온-파인드를 통해 정점들의 집합을 확인한다. 이때, 그래프가 사이클을 형성 하지 않은 트리의 개수만 필요하므로, 사이클을 형성할 경우 제외 시켜야한다. 

순서는 다음과 같다.

1. 유니온 파인드를 통해 노드의 부모요소를 확인한다.

2. 유니온 파인드를 통해 확인한 루트 노드가 동일할 경우 이미 사이클을 형성 한것으로 트리에서 제외한다.

3. 각 원소가 속한 집합을 다시 확인하고, 사이클을 형성한 그래프의 루트 노드를 제외한 값을 구한다.

각 트리의 루트 노드를 찾은 뒤, 사이클을 형성한 그래프의 루트 노드(그래프는 루트 노드가 없으나, 유니온파인드를 통해 찾은 가장 낮은 정점을 루트 노드로 표현)를 제거하면 문제의 값이 나온다.

트러블 슈팅

처음 이 문제를 풀이했을 때, 계속해서 16%에서 틀렸다고 나타났다. 놓친 부분이 사이클을 형성한 노드를 포함한 그래프를 제외하는 것을 고려하지 못하였고, 해당 부분을 구하기 위해 노드를 저장하는 배열을 추가, 그리고 중복을 제거하기 위해 셋 구조를 활용하여 해결하였다.

구현

const filePath =
  process.platform === "linux" ? "/dev/stdin" : "examples/트리.txt";

let input = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n")
  .map((i) => i.split(" ").map(Number));

const findParent = (parent, x) => {
  if (parent[x] != x) {
    return findParent(parent, parent[x]);
  }
  return parent[x];
};

const unionParent = (parent, a, b, cycled) => {
  a = findParent(parent, a);
  b = findParent(parent, b);
  if (a === b) cycled.push(a);
  if (a < b) parent[b] = a;
  else parent[a] = b;
};

function solution(N, M, graph) {
  let answer = 0;
  const cycled = [];
  const parent = Array.from({ length: N + 1 }, (_, i) => i);
  for (const [a, b] of graph) {
    unionParent(parent, a, b, cycled);
  }
  const parentSet = new Set();
  for (let i = 1; i < N + 1; i++) {
    const x = findParent(parent, i);
    parentSet.add(x);
  }
  const newCycled = new Set();
  for (const x of cycled) {
    const k = findParent(parent, x);
    newCycled.add(k);
  }
  answer = [...parentSet].length - [...newCycled].length;

  return answer;
}

let idx = 0,
  test = 1;

while (true) {
  const [N, M] = input[idx];
  if (N === 0 && M === 0) break;
  const graph = input.slice(idx + 1, idx + 1 + M);
  treeCount = solution(N, M, graph);
  if (treeCount > 1) {
    console.log(`Case ${test}: A forest of ${treeCount} trees.`);
  } else if (treeCount === 1) {
    console.log(`Case ${test}: There is one tree.`);
  } else {
    console.log(`Case ${test}: No trees.`);
  }
  idx += M + 1;
  test++;
}

메모리: 76220KB, 시간: 556ms

반응형