백준 1068 C++

처음에는 다음과 같은 코드를 제출했다.

예시도 문제없이 통과하고 제출했을 때 %도 쭉쭉 오르다가 77%에서 틀렸다.

#include <iostream>
#include <vector>

using namespace std;

int n; int removeNode;
vector<vector<int>> tree(51);
int leafCount = 0;
int root;
int visited[51];

void dfs(int s)
{
	if (visited[s] == 1) {
		return;
	}

	if (tree[s].size() == 0) {
		if (s == removeNode) return;
		leafCount++;
		return;
	}

	for (auto i : tree[s]) {
		dfs(i);
	}
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a; cin >> a;
		if (a == -1) {
			root = i;
			continue;
		}

		tree[a].push_back(i);
	}

	cin >> removeNode;

	tree[removeNode].clear();
	dfs(root);
	cout << leafCount;
}

 

 

그럼 왜 틀린건가? 계속 생각을 해보다가

예외가 이런 상황이 있었다.

그림이 엉망이긴 한데 위와 같은 트리가 주어졌을 때 7이 removeNode로 선정이 된다면 leafNode의 수는 6을 포함하지 않는다.

왜냐면 tree[6].size() -> 1이기 때문이다. 그래서 leafNode++이 되지 않아서 문제가 틀렸던것으로 예상된다.

그래서 다음과 같은 로직으로 바꿔서 문제에 통과했다.

 

 

#include <iostream>
#include <vector>

using namespace std;

int n; int removeNode;
vector<vector<int>> tree(51);
int leafCount = 0;
int root;
int visited[51];

void dfs(int s)
{
	if (visited[s] == 1) {
		return;
	}
	visited[s] = 1;

	if (s == removeNode) return;

	if (tree[s].size() == 0) {
		//cout << s << " is size 0 \n";		//여기서 바로 reture이 되니까 문제다.... 하지만 여기서 바로 return 하지 않는다면 다른 로직이 꼬인다.
		//자식 노드가 하나있을 때 삭제가 되면 문제가 생긴다. 결국 자식이 하나가 있고 해당 자식이 removeNode라면 자신도 leaf가 되지만 자신의 vector안에는 removeNode가 들어가있기 때문에 leafCount++을 하지 못한다.
		leafCount++;
		return;
	}

	for (auto i : tree[s]) {
		dfs(i);
		//위의 if와 같은 문제가 발생하기에 다음과 같은 로직을 추가했다.
		if (i==removeNode && tree[s].size() == 1) {			//temp == -1 -> 앞에서 했던 dfs의  i가 removeNode일때 / tree[s].size()==1 -> 근데 그 트리에 요소가 removeNode뿐이야. 그럼 leafCount++을 한다.
			leafCount++;
		}
	}
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a; cin >> a;
		if (a == -1) {
			root = i;
			continue;
		}

		tree[a].push_back(i);
	}

	cin >> removeNode;

	tree[removeNode].clear();
	dfs(root);

	cout << leafCount;
}

 

 

다음과 같이 dfs내부의 for를 통해 해당 트리에 removeNode가 존재하는지 찾아주고

존재하고 해당 트리의 size가 1이라면 자신(s)이 leafNode가 되기 때문에 leafCount++을 해준다.