[백준 node.js] 11725번_트리의 부모 찾기

백준 DFS 알고리즘 11725번_트리의 부모 찾기

난이도 : 실버II

해결못한 문제 : 시간초과

 

문제 설명

입출력

 

문제 풀이 : 이 문제는 인접 그래프 형식의 문제이다. 배열의 인덱스 자체가 노드번호를 의미하고 배열의 값이 그 노드와 인접한 다른 노드들의 인덱스번호가 들어있는 셈이다. 예를들어 [1, 6], [6, 3] 의 연결 정보가 주어졌을때  양방향 이므로 graph배열 1번의 인덱스에 6번의 값이 있고 반대로 인덱스6번에는 1과 3의 값이 있고 인덱스3에는 6번의 값이 있는 셈이다. 이해가 안된다면 인접그래프를 검색해서 원리를 찾아보면 이해가 갈 것이다.

 

다시 문제로 돌아가서 인접그래프로 값을 지정해준 후, 방문처리를 위한 배열, 부모노드를 담는 배열을 선언해준 후,

graph의 1번 인덱스부터 반복문을 통해(문제에서 루트가 1이라고 했으므로 ) 해당 요소들을 전부 방문처리하고 부모의 값을 넣어준다. 이렇게 모든 방문처리가 끝난 후 2번 인덱스부터 부모의 요소를 출력해주면 된다.

 

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

let input = [];
let graph = [];
rl.on("line", function (line) {
  //여러줄 입력
  input.push(line);
}).on("close", function () {
  let n = Number(input.shift());

  graph = Array.from(Array(n + 1), () => new Array());

  //양방향 인접그래프
  for (let i = 0; i < input.length; i++) {
    let [x, y] = input[i].split(" ").map((el) => Number(el));
    graph[x].push(y);
    graph[y].push(x);
  }

  //노드 방문처리
  let visited = new Array(n + 1).fill(false);
  //재귀로직 대신 스택 이용
  let stack = [1];
  //부모의 노드를 가지는 배열
  let parent = new Array(n + 1);

  //반복문을 돌면서 인접노드를 방문처리하고 스택에 넣고
  //부모의 노드를 삽입
  while (stack.length !== 0) {
    let tmp = stack.shift();
    for (let j of graph[tmp]) {
      if (visited[j] === false) {
        visited[j] = true;
        parent[j] = tmp;
        stack.push(j);
      }
    }
  }

  //부모 노드 출력
  for (let k = 2; k < n + 1; k++) {
    console.log(parent[k]);
  }
  process.exit();
});

 

* 제출 시도시 계속 시간 초과 판정이 뜬다.  파이썬을 이용하여 해결한 풀이방식을 보고 그대로 옮겼음에도 JS로 도전시 시간 초과판정이 떴다. 검색을 해보니 여러사람들도 시간 초과판정으로 인해 질문이 많은걸 보고 그냥 풀이방식만 익히고 넘어갔다... 아마도 스택처럼 사용할려고 push, pop같은 곳에서 시간복잡도가 높아져서 그런거같다.