백준2668 - 숫자고르기 (DFS) node.js

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

 

문제 풀이 방식

먼저 각 노드 별로 어떤 노드와 연결되어 있는지 객체 테이블에 저장해두는 것이 시작.

다음 문제를 푸는 것에 있어, 시작 노드에서 출발해 연결된 노드를 순회할 때 시작 노드에 도달할 수 있는지가 중요했다.

따라서, 깊이우선탐색(재귀로 접근)으로 탐색하는 과정에 있어, 시작점을 기억하기 위해, 시작점을 재귀함수에 전달인자로 전달할 필요가 있었다. (물론 전역 변수로 저장해도 상관 없다.)

 

재귀 함수는 다음과 같이 구현했다.

다음 노드를 방문한 적이 있는지 확인했고, 방문한 적이 없다면 다시 재귀 함수로 진입.

만약 다음 노드가 방문한 적이 있고 시작점과 같다면, 이를 결괏값에 추가시켰다.

(만약 위 두 조건을 만족하지 못할 시 함수 종료)

 

전체 소스 코드

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

function solution(data) {
  const [n, ...arr] = data.map(Number);

  const table = {},
    result = [];

  arr.forEach((el, idx) => (table[idx + 1] = el));

  let visited;

  function recursive(cnt, def) {
    visited[cnt] = true;
    const next = table[cnt];

    if (!visited[next]) recursive(next, def);
    else if (visited[next] && next === def) result.push(next);
  }

  for (let i = 1; i <= n; i++) {
    visited = Array.from({ length: n + 1 }, () => false);
    recursive(i, i);
  }

  result.sort((a, b) => a - b);
  console.log(result.length);
  console.log(result.join("\n"));
}

solution(input);