Node.js) 백준 16947번: 서울 지하철 2호선

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

16947번: 서울 지하철 2호선

const fs = require("fs");
const input = fs.readFileSync("./dev/stdin").toString().trim().split("\n");
const N = +input.shift();
const subway = input.map((v) => v.split(" ").map((x) => Number(x) - 1));

const edge = Array.from(Array(N), () => []);

subway.forEach((v) => {
  const [v1, v2] = v;
  edge[v1].push(v2);
  edge[v2].push(v1);
});

let visited = new Array(N).fill(false);
let cycle = new Array(N).fill(false);

// 싸이클 찾는 함수
const checkCycle = (start, now, prev) => {
  if (cycle[start]) return;

  const next = edge[now];
  const nextL = next.length;

  for (let i = 0; i < nextL; i++) {
    if (next[i] == prev) continue;

    if (next[i] == start) {
      visited.forEach((v, index) => {
        if (v) {
          cycle[index] = true;
        }
      });
      return;
    } else if (!visited[next[i]]) {
      visited[next[i]] = true;
      checkCycle(start, next[i], now);
      visited[next[i]] = false;
    }
  }
};

const calcDist = (start) => {
  let q = [];
  visited = new Array(N).fill(false);
  q.push([start, 0]);
  visited[start] = true;

  while (q.length > 0) {
    const [now, cnt] = q.shift();
    if (cycle[now]) return cnt;
    const next = edge[now];
    const nextL = next.length;

    for (let j = 0; j < nextL; j++) {
      if (visited[next[j]]) continue;
      else {
        q.push([next[j], cnt + 1]);
        visited[next[j]] = true;
      }
    }
  }
};

// 싸이클 찾기
for (let i = 0; i < N; i++) {
  if (cycle[i]) continue;
  visited[i] = true;
  checkCycle(i, i, -1);
  visited[i] = false;
}

const answer = [];

//싸이클까지 거리 계산
for (let i = 0; i < N; i++) {
  answer.push(calcDist(i));
}

console.log(answer.join(" "));