백준 1068번 트리 C++ 깊이 우선 탐색, DFS, 트리

리뷰

쉽게 생각했다가 푸는데 한시간은 걸린 문제 생각지 못한 까다로운 조건이 많다. 이래서 설계를 하고 풀어야 하는데..

 

문제 풀이

n개의 줄에 노드간 상관 관계를 받아준다. -1이 주어졌을땐 해당 인덱스를 루트 인덱스로 따로 저장해 주자

인접 리스트 형태가 완료 되었다면 삭제할 값을 받아오고 해당 인덱스의 벡터를 날려주자

루트 인덱스부터 dfs를 시작한다. 이때 루트가 비어있다면 리턴을 해주자 (루트가 삭제된 케이스)

현재 노드의 자식을 순회하고, 만약 삭제된 노드를 만났는데 현재 노드의 크기가 1일 경우 cnt를 1개 올린다.

자식의 리스트가 비어있다면 cnt를 올리고 다음 요소를 순회한다.

둘 다 해당되지 않으면 해당 인덱스를 dfs 해준다. dfs가 전부 종료되면 cnt를 출력해 준다.

 

참고 사항

참고해야할 조건들은 다음과 같다.

1. 루트가 삭제된 경우
2. 루트가 리프 노드가 될 수도 있는 경우
3. 삭제된 노드를 만났을때 처리할 로직

 

정답 코드

#include <iostream>
#include <vector>

using namespace std;

int n, e, rt, cnt;
vector<vector<int>> lst;

void dfs(int index) {
	if (lst[index].empty()) return;
	for (int i : lst[index]) {
		if (i == e) {
			if (lst[index].size() == 1) cnt++;
			continue;
		}
		if (lst[i].empty()) {
			cnt++;
			continue;
		}
		dfs(i);
	}
}

int main() {
	cin >> n;
	lst.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> e;
		if (e == -1) rt = i;
		else lst[e].push_back(i);
	}
	cin >> e;
	lst[e].clear();
	dfs(rt);
	cout << cnt;
}