글 읽기 - 코드 한 번만 봐주실분

p_ce1052 4년 전 0

각 줄에 주석을 달아놨습니다. 주석 달면서 계속 생각해봤는데 어디가 틀렸는지 잘 모르겠습니다. 쓸데없는 정보지만 80퍼쯤에서 틀렸습니다가 뜨더라구요 어떤 반례가 있을까요? 입력은 사이클없는 1개의 컴포넌트로 되어있는 그래프 = 트리1개 라고 가정했습니다

#include<iostream>
#include<vector>
using namespace std;
vector<vector<int> > graph; //인접리스트로 그래프 표현 
vector<bool> visited; //dfs 를 위한 방문배열 
int leaf_node[50]; //각 노드가 가진 리프노드 자기 자신이면 1 

int dfs(int node){ // 자신을 루트로 하는 트리의 리프노드 개수 반환 
	visited[node]=true; //방문함 
	int ret=0; //리프노드 개수  
	for(int i=0; i<graph[node].size(); i++){ 
		//방문 안 된 자식이 있다면 구해와서 더한다 
		if(!visited[graph[node][i]]) ret+=dfs(graph[node][i]);
	}
	//자식이 있다면 무조건 양수를 반환하므로 ret이 0이라는 것은 리프노드라는 뜻 
	return leaf_node[node]=(ret==0?1:ret);  //리프노드면 1, 아니면 ret을 저장 후 반환 
}
int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin>>n;
	graph=vector<vector<int> >(n);
	visited=vector<bool>(n,false);
	int temp,start;
	for(int i=0; i<n; i++){
		cin>>temp;
		if(temp==-1) start=i; //i노드가 루트이므로 루트부터 탐색하기 위해 표시  
		else graph[temp].push_back(i); //i노드의 부모가 temp이므로 temp의 자식은 i임  
	}
	dfs(start); //start가 루트인 트리의 리프노드 계산  
	cin>>temp; //제거 노드  
	//start를 루트로 하는 트리의 리프노드 - 제거대상이 가진 섭트리의  리프노드 개수  
	cout<<leaf_node[start]-leaf_node[temp]; 
}

p_ce1052 4년 전 0

해결했습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

코드 한 번만 봐주실분

p_ce1052 4년 전 0

p_ce1052 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말