11725번: 트리의 부모 찾기

백준에서 11725번: 트리의 부모 찾기 (난이도: Silver II) 확인하기

1. 문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

1-1. 입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

1-2. 출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

2. 풀이

2-1. 코드

const [N, ...edges] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

const graph = Array.from({ length: +N + 1 }).map(() => []);
const checked = Array.from({ length: +N + 1 }).fill(false);
const parentNodes = Array.from({ length: +N + 1 }).fill(null);

edges.forEach(edge => {
  const [start, end] = edge.split(' ');

  graph[start].push(+end);
  graph[end].push(+start);
});

const dfsSearchForParent = vertex => {
  if (checked[vertex]) return;

  checked[vertex] = true;

  graph[vertex].forEach(child => {
    if (!checked[child]) parentNodes[child] = vertex;

    dfsSearchForParent(child);
  });
};

dfsSearchForParent(1);

let answer = '';

for (let i = 2; i < parentNodes.length; i++) {
  answer += parentNodes[i] + '\n';
}

console.log(answer);

2-2. 접근 방식

• 제공된 노드 정보를 기준으로 그래프를 만들었다. 이때 N + 1 길이의 배열을 사용한 이유는 노드 번호를 인덱스로 활용하기 위함이다.
• 1을 트리 루트로 가정하기 때문에 1을 넘겨주면 재귀적으로 트리를 탐색하며 2번 노드부터 순차적으로 각 노드의 부모 노드를 찾는 DFS 알고리즘을 구현했다.
• 처음에는 노드 간의 양방향 관계를 나타내는 그래프에서 어떻게 자식 노드가 아닌 부모 노드만 식별해낼지에 대한 고민이 있었지만, 루트 노드와 연결되어 있는 노드의 부모는 무조건 루트 노드임을 발견하게 되면서 (즉, 문제에서 제공되는 첫 번째 Test Case의 경우, 6과 4번 노드는 무조건 부모 노드가 1이다), 금방 재귀적으로 호출될 로직을 세울 수 있었다.
• 루트 노드의 자식 노드들을 순회하면서, 각 자식 노드의 번호에 해당하는 그래프 인덱스에 접근해, 자식 노드와 연결되어 있지만 아직 방문하지 않은!checked[vertex], 즉 탐색 중인 노드의 부모 노드가 아닌 것들은 탐색 중인 노드의 자식 노드로 판단했다.
• 각 노드의 부모 노드 번호는 parentNodes라는 배열에 담아뒀고, 마지막에 parentNodes 배열을 순회하면서 각 부모 노드의 번호를 answer 변수에 추가한 뒤 answer 변수를 출력했다.

2-3. 회고

• 이번 문제에 시간을 생각보다 많이 썼는데, 주요 원인은 마지막에 parentNode 배열에 담긴 값을 하나하나 출력했기 때문이었다. 이렇게 하는 경우 무조건 시간 초과가 뜨는데, console.log 때문에 시간 초과가 뜬다고는 생각 못하고 괜히 문제 없는 로직만 계속 수정하다가 많은 시간을 낭비했다.

참고: "console.log is slow"