백준 1068 c++ "트리" -PlusUltraCode-

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

 

 

[필자 사고]

트리의 리프노드를 구하라는 문제이다.

마지막에 특정 노드를 삭제할 경우 밑의 자식 노느들 또한 삭제된다.

 

필자는 리스트형태 및 DFS알고리즘을 통해 트리의 리프 노드를 구하는 식으로 문제를 해결했다.

 

다만 여기서 조심해야 될 점은 루트노드가 반드시 0이라는 보장이 없다는 점이다.

-1의 입력이 1번 2번 idx 3번 idx 일지는 아무도 모르기 때문에 이 부분 실수 없길 바란다.

 

또한 트리의 계층구조가 있기 때문에 양방향이아닌 단방향으로 리스트를 만들어줘야 된다.

아래는 소스코드 해설이다.

 

1. Input 함수:

여기서 목표 노드에서 출발하기 전에 트리의 구조를 큐(arr)에 저장합니다. 각 노드는 부모 노드와 연결된 자식 노드의 정보를 가지고 있습니다.

• Root 노드 설정: 입력을 통해 부모 노드가 -1이면 해당 노드를 트리의 루트 노드로 설정합니다. 이 루트 노드는 탐색의 시작점이 됩니다.
• 삭제할 노드 설정: 마지막 입력으로 삭제할 노드를 설정하여 탐색 대상에서 제외할 준비를 합니다.

큐에 트리 구조를 저장하고 탐색할 준비를 마친 후, 삭제할 노드를 removeNode로 지정합니다.

2. DFS 함수:

루트 노드에서 출발하여 큐에서 최장 경로를 탐색하는 방식입니다. DFS는 현재 노드가 이미 방문되었는지 확인한 후, 방문되지 않은 경우에만 그 노드에서 출발합니다.

• 각 노드에서 연결된 다음 노드(next)로 이동하며, 연결된 자식 노드가 없다면 그 노드를 리프 노드로 간주하고 leafCount를 증가시킵니다.
• 탐색 중 방문 가능한 노드가 없으면 "최장 시간일 때" 리프 노드에 도달했다는 의미입니다.

DFS는 연결된 모든 노드를 순회하며 리프 노드를 찾고, 그 과정에서 삭제된 노드는 방문하지 않도록 설정합니다.

3. GameStart 함수:

탐색을 시작하기 전에 큐에서 removeNode로 설정된 노드를 방문 처리하여 탐색 대상에서 제외합니다. 이후, 목표 노드(루트 노드)에서 출발하여 DFS를 실행하고, 최장 경로를 따라 리프 노드를 탐색합니다.

탐색이 끝난 후, 삭제된 노드를 제외한 리프 노드의 개수를 출력합니다.

 

 

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> arr;
vector<bool> visited;

int N;
int removeNode;
int leafCount = 0;
int rootNode = 0;

void Input() {
	cin >> N;
	arr.resize(N);
	visited.resize(N);

	for (int node = 0; node < N; node++) {
		int parent;
		cin >> parent;
		if (parent == -1) {
			rootNode = node;
			continue;
		}
		arr[parent].push_back(node);
		
	}

	cin >> removeNode;
}

void DFS(int start) {
	if (visited[start])return;
	
	visited[start] = true;
	int flag = 0;

	for (int next : arr[start]) {
		if (visited[next] == false) {
			DFS(next);
			flag = 1;
		}
	}

	if (flag == 0)leafCount++;
}


void GameStart() {
	visited[removeNode] = true;
	DFS(rootNode);
	cout << leafCount;
}

int main(void) {
	Input();
	GameStart();
}