1068 트리 질문

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

해결된 질문

작성

133

루트 노드부터 시작해서 자식 노드의 개수 만큼 cnt에 더해주고 그 자식노드 중에 또 자식이 있으면 -1 해주는 방식으로 구현했습니다. 백준에 제출했을 때 78% 에서 틀렸다고 뜨는데 ... 놓친 부분을 잘 모르겠습니다.

아래는 저의 코드입니다.

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n;
int cnt;
queue<int> q;
int root;
bool vst[54];
int main(void){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	vector<int> v[n];
	for(int i=0; i<n; i++){
		int x;
		cin >> x;
		if(x == -1){
			q.push(i);
			root = i;
		}
		else{
			v[x].push_back(i);
		}
	}
	int rn;
	cin >> rn;
	if(rn == root){
		cout << 0;
		return 0;
	}
	if(n == 2){
		cout << 1;
		return 0;
	}
	vst[rn] = 1;
	for(auto e: v[rn]){
		vst[e] = 1;
	}
	while(!q.empty()){
		auto cur = q.front(); q.pop();
		if(vst[cur]) continue;
		cnt += v[cur].size();
		if(!v[cur].empty()) cnt--;
		for(int j=0; j < v[cur].size(); j++){
			if(vst[v[cur][j]]) continue;
			vst[cur] = 1;
			q.push(v[cur][j]);
		}
	}
	cout << cnt;
	return 0;
}

C++코테 준비 같이 해요!

답변 1

큰돌

지식공유자

안녕하세요. HAN님 ㅎㅎ

먼저 루트노드가 remove될 때, 2개일 때 순차적인 예외처리 훌륭합니다.

remove되는 것은 continue로 하는 것은 잘했습니다.

but..

리프노드의 정의는 뭘까요?

자식 노드의 수가 0인 것이죠.

즉, v[node].size() == 0일 때만 cnt++하면 되는 것 아닌가요?

근데 왜 size를 더했다가 cnt를 -를 하는 로직이 필요하죠?

감사합니다.

강사 큰돌 올림.

dongdong

질문자

굳이 사이즈를 더 할 필요없이 size가 0일때만 더해주면 됐군요... 머리를 탁..!

로직을 변경을 해도 계속 78%에서 틀려서 여러 시도 끝에 반례를 찾았습니다

input

-1 0 1 2

output

1 이 나와야함 // 제 코드는 0이 나오더군요

트리가 직선 모양 일 때 잘못된 답이 나왔습니다.

그래서 vst배열을 사용하지 않고 v[지우는 노드].clear() 로 size를 0으로 만들어준 뒤 v[지우는노드] 를 부모로 가지는 자식 노드들도 벡터에서 지워주었습니다.

아래는 저의 코드입니다

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n;
int cnt;
queue<int> q;
int root;
int main(void){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	vector<int> v[n];
	for(int i=0; i<n; i++){
		int x;
		cin >> x;
		if(x == -1){
			q.push(i);
			root = i;
		}
		else{
			v[x].push_back(i);
		}
	}
	int rn;
	cin >> rn;
	if(rn == root){
		cout << 0;
		return 0;
	}
	if(n == 2){
		cout << 1;
		return 0;
	}
	v[rn].clear();
	for(int i=0; i<n; i++){
		for(int j=0; j<v[i].size(); j++){
			if(v[i][j] == rn) v[i].erase(v[i].begin()+j);
		}
	}
	while(!q.empty()){
		auto cur = q.front(); q.pop();
		for(int j=0; j < v[cur].size(); j++){
			cnt += (v[v[cur][j]].size() == 0);
			q.push(v[cur][j]);
		}
	}
	cout << cnt;
	return 0;
}

큰돌

지식공유자

음... 이 코드 혹시 맞나요? / 제가 보기에는... 한단계밖에 조사를 하지 않는 거같아요. 자 예를 들어서 1 2 3 4가 일자로 연결되어있고(1 - 2 - 3 - 4 / 4가 가장 부모노드) 4가 remove 노드라면 어떻게 되나요? 단순히 2중 for문으로 해당 부분이 다 제거가 안 될 것같아요. 예를 들어 1 - 2 가 제거가 되나요?

지금 "제거"하는 로직 자체가 올바르게 되지않았다는 말씀을 드리구요.

"제거" 문제는 사실 굉장히 까다로워요. 꼭 필요한 경우에는 "제거" 로직을 넣지만 보통은 제거 보다는 "표기"를 해서 해당 부분에 대한 로직을 진행하지 않거나 하는 경우로 합니다. :)

감사합니다.

강사 큰돌 올림.

dongdong

질문자

제출 했을때는 정답처리가 되었습니다. 아하..! 저는 항상 부모노드가 자식노드 보다 작은 수를 가진다고 생각하고 문제를 풀었습니다. 문제에서는 부모노드는 자식노드보다 숫자가 작다 라는 조건이 없군요... 표기 방식 머릿속에 메모해두겠습니다! 많은 공부가 된 거 같습니다 큰돌 강사님. 답변 감사합니다 !!

인프런 커뮤니티 질문&답변

1068 트리 질문