트리의 부모 찾기

문제

언어

  • JavaScript

순서도

  1. 그래프 생성
  2. BFS 탐색

문제 풀이 step 1

  • 각 노드의 부모 노드를 찾아주는 문제입니다.
  • 간단하게 BFS 탐색으로 풀 수 있습니다.
  • 왜 BFS 탐색으로 풀 수 있을까요??
    • Tree 는 계층적인 자료를 표현하는 자료구조입니다. 그리고 Tree 의 어떤 노드의 부모 노드는 한 계층 바로 위에 직접적으로 연결되어 있는 노드입니다.
    • 그리고 BFS 탐색은 한 단계씩 계층을 생성하는 듯한 형태를 띄며 탐색을 합니다.
    • 그래서, 루트 노드에서 BFS 탐색을 하며 한 계층씩 내려가면서 각 노드의 부모 노드를 기록해줄 수 있기 때문에 BFS 탐색으로 풀 수 있습니다.

문제 풀이 step 2

  • 우선 주어진 입력으로 인접리스트 형식의 그래프를 생성합니다.
    • 트리도 그래프이기 때문에 그래프 표현 방식을 사용할 수 있습니다.
  • 생성한 그래프를 시작 노드를 1 번 노드로 해서 BFS 탐색을 실시합니다.
    • parents 배열을 하나 준비합니다.
    • 매 탐색시, 이전 노드를 기록합니다. 그 이전 노드가 탐색할 노드의 부모 노드입니다.
    • 저는 부모 노드를 기록하는 것으로 방문 처리를 대신했습니다.
  • BFS 탐색을 통해 부모 정보가 채워진 parents 배열을 출력 양식에 맞게 출력하면 정답입니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

class Queue {
	constructor() {
		this.bucket = [];
		this.front = -1;
		this.rear = -1;
	}

	isEmpty() {
		return this.front === this.rear;
	}

	enqueue(data) {
		this.bucket[++this.rear] = data;
	}

	dequeue() {
		if (this.isEmpty()) return;
		return this.bucket[++this.front];
	}
}

const BFS = (graph, start, parents) => {
	const queue = new Queue();

	queue.enqueue(start);
	parents[start] = -1;

	while (!queue.isEmpty()) {
		const from = queue.dequeue();

		for (let i = 0; i < graph[from].length; i++) {
			const to = graph[from][i];

			if (parents[to] !== undefined) continue;

			queue.enqueue(to);
			// 이전 노드를 기억해서 탐색할 노드의 부모 노드로 기록하기
			parents[to] = from;
		}
	}
};

const solution = (input) => {
	const n = parseInt(input[0]);

	// 인접리스트 형식의 그래프 생성
	const graph = Array.from({length: n + 1}, () => []);
	for (let i = 1; i < n; i++) {
		const [from, to] = input[i].split(" ").map(Number);

		graph[from].push(to);
		graph[to].push(from);
	}

	const parents = [-1];
	BFS(graph, 1, parents);

	return parents.slice(2).join("\n");
};

console.log(solution(input));