[백준 / C++] 1068번: 트리 (DFS)

 

 

 

 

https://www.acmicpc.net/problem/1068

1068번: 트리

 

난이도: solved.ac 골드 5

 

 

알고리즘 분류

그래프 탐색 (DFS)

 

구현 방법

부모 노드의 번호를 index로 갖는 벡터에 해당 자식 노드의 번호를 저장한다.

(Ex. 4번 노드의 부모가 2면, graph[2].push_back(4))

 

그리고 삭제할 노드의 번호를 입력받는데, 삭제할 노드가 루트 노드라면 트리는 아예 없어지므로 0을 출력하게 한다.

삭제할 노드가 루트 노드가 아니라면 DFS 함수를 실행한다.

 

DFS 탐색을 하다가 특정 노드가 삭제할 노드를 자식으로 갖는다면 일단 삭제할 노드가 위치한 index를 저장하고, 삭제할 노드로의 탐색은 하지 않고 그 노드를 벡터에서 삭제한다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int N, del, ans;
vector<int> graph[50];
void DFS(int x);

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int root, num;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> num;
		if (num == -1) {
			root = i;	// 루트 노드 번호 저장
			continue;
		}
		graph[num].push_back(i);
	}
	cin >> del;	// 삭제할 노드
	if (del != root) {
		DFS(root);
		cout << ans;
	}
	else
		cout << 0;	// root를 삭제하는 경우
}

void DFS(int x) {
	int del_idx = -1;
	for (int i = 0; i < graph[x].size(); i++) {
		if (graph[x][i] == del) {
			del_idx = i;	// 삭제할 노드 저장
			continue;	// 삭제할 노드는 탐색 X
		}
		DFS(graph[x][i]);
	}
	if (del_idx > -1)
		graph[x].erase(graph[x].begin() + del_idx);
	// 해당 노드로의 길 삭제
	if (graph[x].empty())
		ans++;	// 자식 노드가 없으면 리프 노드이므로
}

 

성능

코드 제출 결과