[C++] 백준 1068번 트리

그래프 탐색 문제. 그 중에서도 트리 & DFS문제이다.

트리의 기본 개념만 안다면 쉽게 풀 수 있다.

조건을 하나 잘못 생각해서 틀렸었다.

 

문제풀이

어려운 것 없이, 

부모 - 자식, 자식 - 부모 관계를 모두 저장해둔다. 그리고 각각 다음에 사용한다.

• 부모 - 자식 관계 : 트리에서 깊이 우선 탐색을 통해 리프 노드가 몇 개인지 구할 때 사용한다.
• 자식 - 부모 관계 : 지울 노드의 부모 노드의 번호를 구하고 해당 부모 노드에서 부모 - 자식 관계에서 지울 노드를 찾은 후 지울 때 사용한다.

 

루트 노드가 예시 케이스에서는 -1이 모두 첫번째로 나오긴 했지만,

나중에 나오는 경우를 대비해서도 코드를 구현했다.

 

/*
* 백준 1068번 트리
* https://www.acmicpc.net/problem/1068
* 그래프 탐색 - 깊이 우선 탐색 / 트리
*/
#include <iostream>
#include <vector>
using namespace std;

int rootNodeNum;
int nodeCnt;
int deleteNodeNum;
vector<int> childNode[50];
int parNode[50];
int ans;

void order(int nodeNum) {
	//틀린 이유 : 그냥 지울 노드에 도착했을 경우 return하도록 했었음.
	if (childNode[nodeNum].size() == 0) {
		ans++;
		return;
	}
	else {
		for (int child : childNode[nodeNum]) {
			order(child);
		}
	}


}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> nodeCnt;

	int parNodeNum;
	for (int i = 0; i < nodeCnt; i++) {
		cin >> parNodeNum;
		if (parNodeNum == -1) {
			rootNodeNum = i;
			continue;
		}
		childNode[parNodeNum].push_back(i);
		parNode[i] = parNodeNum;
	}

	cin >> deleteNodeNum;

	if (deleteNodeNum != rootNodeNum) {
		//해결책 - 지울 노드의 부모 노드의 자식 중에서 해당 지울 노드를 지운다.
		int deleteNodeParent = parNode[deleteNodeNum];

		for (int i = 0; i < childNode[deleteNodeParent].size(); i++) {
			if (deleteNodeNum == childNode[deleteNodeParent][i]) {
				childNode[deleteNodeParent].erase(childNode[deleteNodeParent].begin() + i);
				break;
			}
		}

		order(rootNodeNum);
	}


	cout << ans;

	return 0;
}

코드에 주석으로도 달아놨지만, 처음에 내 풀이는

노드를 지워주지 않고 그냥 지울 노드에 도착했을 경우 바로 return하는 식으로 만들었다.

 

그러나 이렇게 할 경우

1-2-3-4 가 연결되고 4를 지웠을 때 리프 노드가 3이 되어야 하는데 3은 자식인 4를 가지고 있다고

판단하므로 리프노드가 되지 않는다.

 

따라서 그냥 모든 정보를 저장해 뒀다가 지울 노드의 정보를 지워주고 DFS 탐색을 했다.

 

 

GitHub - kimyunseok/cpp: my study-record

코드는 위에서 확인 가능하다.