백준3182 - 한동이는 공부가 하기 싫어! (DFS) node.js

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

문제 풀이 방식

깊이 우선 탐색인 DFS 알고리즘을 활용하여, 각 노드에 방문할 때 깊이를 누적하여 반환하고 저장한 뒤, 저장된 데이터에서 가장 높은 값을 가진 인덱스를 답안으로 출력했다.

 

전체 소스 코드

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

function solution(data) {
  const arr = data.map(Number);
  const N = arr[0];
  let visited = Array.from({ length: N + 1 }, () => false);

  function DFS(node, cnt) {
    visited[node] = true;
    const next = arr[node];

    if (!visited[next]) cnt = DFS(next, cnt + 1);
    return cnt;
  }

  const result = Array.from({ length: N + 1 }, () => 0);

  for (let i = 1; i <= N; i++) {
    visited = Array.from({ length: N + 1 }, () => false);
    result[i] = DFS(i, 0);
  }

  const max = Math.max(...result);
  console.log(result.indexOf(max));
}

solution(input);