[boj] 11725. 트리의 부모 찾기 (node.js)

요약

BOJ 11725 트리의 부모 찾기

• 입력: N * M 크기의 미로가 주어진다.
• 출력: (1,1) 에서 (N, M)까지의 최단거리를 구하라.
• 주어진 미로에서 0은 이동할 수 없는 영역으로, 1이 적힌 칸으로만 이동 가능하다.

풀이

• 주어진 트리 구조를 인접 리스트로 변환한다.
• dfs 매개변수로 탐색할 노드와 그 부모 노드를 입력한다. 자식 노드의 인접 리스트를 확인해 부모 노드인 경우는 continue, 자식 노드는 인자를 넣어 또 다시 dfs 탐색한다.

내 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let cnt = 0;
const input = () => stdin[cnt++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  const N = Number(input());
  let linkedList = new Array(N + 1);
  let parents = new Array(N + 1);
  for (let i = 0; i < N + 1; i++) linkedList[i] = new Array();
  for (let i = 0; i < N - 1; i++) {
    let arr = input().split(" ").map(Number);
    linkedList[arr[0]].push(arr[1]);
    linkedList[arr[1]].push(arr[0]);
  }
  dfs(1, -1);
  parents.shift();
  parents.shift();
  console.log(parents.join("\n"));
  process.exit();

  function dfs(node, parent) {
    for (const child of linkedList[node]) {
      if (child == parent) continue;
      parents[child] = node;
      dfs(child, node);
    }
  }
});

• 트리는 인접 리스트를 활용하는 것이 공간복잡도상 효율적이다.
• visited 배열을 활용하는 대신 부모 노드를 매개변수로 활용하였다. 트리는 부모가 한 번에 하나씩이기 때문에 가능하다.