[백준] JavaScript - 트리 (1068)

개요

문제 이름: 트리 (1068)
문제 링크: https://www.acmicpc.net/problem/1068
플랫폼: 프로그래머스/백준
알고리즘 분류: 트리, DFS
소요 시간: 1시간 30분

 

문제 전문

설명

 

입출력

 

문제 풀이

해설

이 문제는 트리의 리프 노드 개수를 구하는 문제로, 깊이 우선 탐색(DFS) 알고리즘을 사용하여 해결할 수 있습니다. 주어진 트리에서 특정 노드를 삭제한 후 남은 트리의 리프 노드 개수를 세는 것이 목표입니다.

 

문제에서 요구하는 사항을 정리하면 다음과 같습니다.

1. 트리의 노드 개수 N이 주어진다. (N은 50 이하의 자연수)
2. 0번 노드부터 N-1번 노드까지 각 노드의 부모 노드 정보가 주어진다. 루트 노드는 -1로 표시된다.
3. 삭제할 노드 번호가 주어진다.
4. 주어진 트리에서 삭제할 노드를 제거하고, 남은 트리의 리프 노드 개수를 출력한다.

문제 풀이 방식은 다음과 같습니다.

1. 입력으로 받은 부모 노드 정보를 이용해 트리 구조를 생성한다. 이때 각 노드의 자식 노드들을 저장하는 2차원 배열을 사용한다.
2. 루트 노드를 찾아 저장한다.
3. 리프 노드의 개수를 세는 재귀 함수를 구현한다.
   • 현재 노드가 삭제할 노드이면 0을 반환한다.
   • 현재 노드가 리프 노드이면 1을 반환한다.
   • 각 자식 노드에 대해 재귀적으로 리프 노드 개수를 세어 누적한다.
   • 모든 자식이 삭제되었다면 현재 노드가 리프 노드가 되므로 1을 반환한다.
4. 루트 노드가 삭제되면 전체 트리가 삭제되므로 0을 반환한다.
5. 루트 노드부터 시작하여 리프 노드 개수를 계산하고 출력한다.

그렇기에 이 문제에서는 DFS를 사용하여 트리를 탐색하며 리프 노드의 개수를 세는 것이 핵심입니다. 삭제할 노드를 만나면 해당 노드와 그 자손 노드들은 더 이상 탐색하지 않고 0을 반환하여 삭제된 것으로 처리합니다. 리프 노드를 만나면 1을 반환하여 개수에 포함시키고, 중간 노드에서는 자식 노드들의 리프 노드 개수를 누적하여 반환합니다.

 

시도

1차 시도  (성공)

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

// 노드의 총 개수
const N = parseInt(input[0]);
// 각 노드의 부모 노드 정보를 배열로 변환
const parents = input[1].split(" ").map(Number);
// 삭제할 노드 번호
const deleteNode = parseInt(input[2]);

function solution(N, parents, deleteNode) {
	// 트리 구조를 저장할 2차원 배열 생성 (각 노드의 자식들을 저장)
	const tree = Array.from({ length: N }, () => []);
	// 루트 노드를 저장할 변수
	let root = 0;

	// 트리 구조 생성
	for (let i = 0; i < N; i++) {
		if (parents[i] === -1) {
			// 부모가 -1이면 루트 노드
			root = i;
			continue;
		}
		// 부모 노드의 자식 배열에 현재 노드 추가
		tree[parents[i]].push(i);
	}

	// 리프 노드의 개수를 세는 재귀 함수
	function countNode(node) {
		// 현재 노드가 삭제할 노드면 0 반환
		if (node === deleteNode) return 0;
		// 자식이 없으면 리프 노드이므로 1 반환
		if (tree[node].length === 0) return 1;

		// 자식 노드들의 리프 노드 개수를 누적할 변수
		let count = 0;
		// 각 자식 노드에 대해 재귀적으로 리프 노드 개수를 세어 누적
		for (let child of tree[node]) {
			if (child !== deleteNode) {
				count += countNode(child);
			}
		}
		// 모든 자식이 삭제되었으면 현재 노드가 리프 노드가 되므로 1 반환
		return count || 1;
	}

	// 루트 노드가 삭제되면 전체 트리가 삭제되므로 0 반환
	if (root === deleteNode) return 0;

	// 루트부터 시작하여 리프 노드 개수 계산
	return countNode(root);
}

// 결과 출력
console.log(solution(N, parents, deleteNode));

위 코드는 다음과 같은 과정으로 문제를 해결합니다.

1. 입력값을 받아와 노드의 개수 N, 부모 노드 정보를 담은 배열 parents, 삭제할 노드 번호 deleteNode를 변수에 저장합니다.
2. 트리 구조를 저장할 2차원 배열 tree를 생성합니다. 이 배열은 각 노드의 인덱스를 키로 하고, 해당 노드의 자식 노드들을 값으로 저장합니다.
3. 부모 노드 정보를 이용하여 트리 구조를 생성합니다. 부모가 -1인 노드는 루트 노드로 별도의 변수 root에 저장합니다.
4. 리프 노드의 개수를 세는 재귀 함수 countNode를 정의합니다.
   • 현재 노드가 삭제할 노드이면 0을 반환합니다.
   • 자식이 없는 노드는 리프 노드이므로 1을 반환합니다.
   • 각 자식 노드에 대해 재귀적으로 countNode를 호출하여 리프 노드 개수를 누적합니다.
   • 모든 자식이 삭제되었다면 현재 노드가 리프 노드가 되므로 1을 반환합니다.
5. 루트 노드가 삭제되는 경우 전체 트리가 삭제되므로 0을 반환합니다.
6. 루트 노드부터 시작하여 countNode 함수를 호출하여 리프 노드 개수를 계산하고 반환합니다.
7. 결과를 출력합니다.

 

시간 복잡도 및 공간 복잡도

• 시간 복잡도: O(N)
  • 트리의 모든 노드를 한 번씩 방문하므로 노드의 개수에 비례하는 시간 복잡도를 가집니다.
• 공간 복잡도: O(N)
  • 트리 구조를 저장하기 위한 2차원 배열과 재귀 호출에 사용되는 스택 공간이 노드의 개수에 비례하므로 O(N)의 공간 복잡도를 가집니다.

 

사용된 주요 메서드

• Array.from(): 유사 배열 객체나 반복 가능한 객체로부터 새로운 Array 인스턴스를 생성합니다.
• Array.prototype.push(): 배열의 끝에 하나 이상의 요소를 추가하고, 배열의 새로운 길이를 반환합니다.
• String.prototype.split(): 문자열을 지정된 구분자를 이용하여 여러 개의 문자열로 나눕니다.
• Array.prototype.map(): 배열 내의 모든 요소 각각에 대하여 주어진 함수를 호출한 결과를 모아 새로운 배열을 반환합니다.
• for...of 문: 반복 가능한 객체(Array, Map, Set, String 등)에 대해서 반복하고, 각 값을 차례로 변수에 할당합니다. 여기서는 자식 노드들을 순회하며 리프 노드의 개수를 세는 데 사용되었습니다.