백준21316 - 스피카 (그래프) node.js

https://www.acmicpc.net/problem/21316

 

문제 해결 방식

별 'Spica'와 연결된 노드는 총 3개며, 연결된 각 노드는 1, 2, 3개의 노드와 연결되어 있다는 특징을 발견하면 어렵지 않은 문제.

그리고 이와 같은 특징은 spica가 유일하기에, 위 조건을 만족하는 노드를 답으로 출력하였다.

(문제에서는 6번 노드가 1개와 연결 | 8번 노드가 2개와 연결 | 3번 노드가 3개와 연결되어 있다.)

 

전체 소스 코드

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt")
  .toString()
  .trim()
  .split("\n");

function solution(data) {
  const edges = data.map((el) => el.split(" ").map(Number));
  const graph = Array.from({ length: 13 }, () => []);

  edges.forEach(([a, b]) => {
    graph[a].push(b);
    graph[b].push(a);
  });

  function act(x) {
    const set = new Set();
    graph[x].forEach((leaf) => {
      set.add(graph[leaf].length);
    });

    return set.size;
  }

  for (let i = 1; i <= 12; i++) {
    if (graph[i].length === 3) {
      const t = act(i);
      if (t === 3) {
        console.log(i);
        return;
      }
    }
  }
}

solution(input);