JXNVCE ALGO-LOG YouJin Jung

BOJ-1068

14 Jul 2021

scpc6 연습문제였던 가까운 곱셈 문제랑 Combination(조합) 관련 백트리킹 문제 풀다가 포기하고 돌아왔다,,,,, 이 문제도 트리인데 구글 없이는 못했을 것 같다… 난 언제 구글 없이 스스로 풀 수 있으려나 😥🙏🏼 아무래도 푸는 양과 강도를 많이 늘려야할 듯 싶다… 틈틈히 찾아보기도 하고…

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

int N, x, deleteNode;
vector <int> v[51];

int find(){
	int answer = 0;
    int temp = 0;

	for(int i=0; i<N; i++){
		if(v[i].size()==0)
			answer=answer+1;
	}
	queue <int> q;
	q.push(deleteNode);

	while(!q.empty()){
		int tmp = q.front();
		if(v[tmp].size()==0){
			temp=temp+1;
		}
		else{
			for(int i=0; i<v[tmp].size(); i++)
				q.push(v[tmp][i]);
		}
		q.pop();
	}

	for(int i=0; i<N; i++){
		for(int j=0; j<v[i].size(); j++){
			if(v[i][j]== deleteNode && v[i].size()==1)
				return answer-temp+1;
		}
	}

	return answer-temp;
}
int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);

	scanf("%d", &N);

	for(int i=0; i<N; i++){
		scanf("%d", &x);
		if(x!=-1) v[x].push_back(i);
	}

	scanf("%d", &deleteNode);
    int result = find();
    printf("%d", result);

    return 0;
}

image

Related posts