[백준 1068] 트리

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

1068번: 트리

#include <cstdio>
#include <list>
int N;
int P[50 + 2];
int D;
int visited[50 + 2];
int root;

std::list<int> Tree[50 + 2];

void input()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &P[i]);
		if (P[i] == -1) root = i;
		else Tree[P[i]].push_back(i);	// 루트가 아니면 인접 리스트 만들어준다.	// 문제에서 친절하게 부모가 주어지는 거라고 알려줌
	}
	scanf("%d", &D);
}

int DFS(int n)
{
	if (n == D) return 0;
	visited[n] = 1;

	for (int nn : Tree[n]) {
		if (visited[nn]) continue;
		visited[n] += DFS(nn);
	}
	return visited[n];
}


int get_leaf()
{
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		if (visited[i] == 1) cnt++;
	}
	return cnt;
}



int main()
{
	input();
	DFS(root);
	int ans = get_leaf();
	printf("%d\n", ans);
	return 0;
}

 

문제 캡쳐하기 귀찮아서 채점 기록으로 대신하는거 아님.. ㅎ 아무튼 아님.. 

 

처음 풀 때는 make_tree 함수 따로 만들어서 input 받고 그 다음에 호출했었다. 그런데 어차피 루트 노드가 아니면 부모 노드에 인접리스트로 줄줄이 엮일 것이기 때문에, 따로 함수를 만들어서 루프 돌리는 것 보다는 데이터를 입력 받으면서 리스트에 push_back 하도록 짜는게 나을 것 같다.

 

 

// DFS( ) 함수

만약 현재 탐색하는 노드가 삭제할 노드이면, 뎁스를 더 깊게 들어가볼 필요 없이 바로 리턴해주어도 된다. 

그렇지 않으면 재귀함수를 돌리면서 몇 개의 자식노드가 있는지 확인한다. (서브트리의 노드 수 세는 문제인 [백준 15681] 트리와 쿼리 문제와 슷비) 

 

 

// get_leaf( ) 함수

만약 방문배열의 값이 1이면 자식 노드가 하나도 없는 잎노드 이므로 if (visited[i] == 1) 일때 cnt 변수를 증가시켜준다.