[백준][dfs] 1068 트리 c++ 구현

목차

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

문제

저번에 풀었지만 더 효율적인 접근을 해보았다..

 

 

bfs를 통한 풀이 방법

https://be-senior-developer.tistory.com/26

[백준] 1068 트리 c++ 구현

 

문제 구현 방향

dfs를 통해 재귀적으로 접근해 리프노드의 수를 누적하는 방식으로 접근해 보았다.

전역 변수를 써서 누적할 수도 있었지만 재귀적인 이해를 통해 누적한 지역변수를 이용했다.

 

 

코드 구현

#include <iostream>
#include <vector>
#include<queue>
#include<algorithm>

using namespace std;
vector<int>v;

int d;
vector<int>adj[100]; //인접리스트 사용


int dfs(int start) { 
	//함수의 호출 방향은 순서대로이지만 종료방향은 거꾸로이기때문에
	//ret의 누적이 되고 누적된 값이 잘 출력된다.. <재귀에 대한 이해>
	int ret = 0;
	int child = 0;
	
	for (int there: adj[start]) {
		if (there == d)
			continue;
		ret +=dfs(there);
		child++;
	}
	if (child == 0)  //자식노드가 0일 경우
		return 1;
	return ret;
}

int main(){
	int n, num, node=1, root;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num;
		if (num == -1)  
			root = i;
		else
			adj[num].push_back(i);
	}
	cin >> d;
	if (d == root) {  //루트노드에 대한 예외처리를 꼭 해주어야 한다
		cout << 0;
	}
	else
	     dfs(root);
}