[백준 11725] 트리의 부모 찾기(자바스크립트)

문제

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

입력

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

출력

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

 

링크: 11725번: 트리의 부모 찾기

---

#풀이 과정

둘째 줄부터 주어지는 값들이 사실상 인접 노드들을 표시한 것이므로 인접 노드부터 탐색하는 너비 우선 탐색을 사용하기로 했다.

 

1. 서로 연결되어 있는 노드들(입력값)을 인접리스트에 저장해 트리를 만든다.

2. 루트 노드인 1부터 큐에 넣고 너비 우선 탐색을 실시해 인접한 노드들을 확인한다.

3. 현재 노드와 연결되어 있는 노드들이 아직 방문한 적 없는 노드라면 방문 처리를 한 뒤 큐에 추가하고, 현재 노드를 부모 노드로 지정한다.

 

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

const N = Number(input[0]);

// 노드 간 연결 관계를 저장하는 인접 리스트 생성
const tree = Array.from(Array(N + 1), () => []);
const visited = Array(N + 1).fill(0);
const parents = [];

// 트리 구성
for (i = 1; i < input.length; i++) {
  const [a, b] = input[i].split(" ").map(Number);
  tree[a].push(b);
  tree[b].push(a);
}

// 너비 우선 탐색으로 부모 찾기
const bfs = () => {
  // 1은 루트 노드이므로 방문했다고 표시
  const queue = [1];
  visited[1] = true;

  while (queue.length) {
    // 현재 노드와 연결된 노드들을 가져와 저장
    const node = queue.shift();
    const child = tree[node];

    // 현재 노드와 연결된 노드들 체크
    for (i = 0; i < child.length; i++) {
      const a = child[i];

      // 해당 노드를 아직 방문하지 않았다면 방문 표시, 큐에 추가, 현재 노드를 부모로 설정
      if (!visited[a]) {
        visited[a] = true;
        queue.push(a);
        parents[a] = node;
      }
    }
  }
};

bfs();
console.log(parents.slice(2).join("\n"));

 

#아쉬운 점

인접 리스트 말고 인접 행렬로 구현할 경우 시간 복잡도가 O(1)이 되는데 리스트 방식에 꽂혀서 행렬로 어떻게 구현해야 할 지 감이 안 잡혔다..