글 읽기 - 왜 안되는지 모르겠습니다...

ryu_eclipse 3년 전 0

early = 특정 노드가 얼리어댑터일때 1

dp[now][0] = sum(dp[next][1] 모든 자식들)

dp[now][1] = min(dp[next][0], dp[next][1])...+.. 모든자식들

이런식으로 했는데, 답이 안나옵니다 ㅠ

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int> > vec;
int visited[1000000+5];
int dp[1000000+5][2];
int n, a,b;
int dfs(int node, int early){

	visited[node] = 1;
	

	dp[node][early]= early;//자기자신 추가 
	
	for(int i=0;i<vec[node].size();i++){
		int next = vec[node][i];

		
		if(early==0)
			dp[node][0] += dfs(next, 1);
		else
			dp[node][1] += min(dfs(next, 0), dfs(next, 1)); 
	}

	
	return dp[node][early];
}


int main(){
	cin>>n;
	vec.resize(n+1);

	for(int i=0;i<n-1;i++){
		cin>>a>>b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}

	int off = dfs(1, 0); //루트가 얼리어댑터가 아닐때 
	int on =dfs(1, 1); //루트가 얼리 어댑터 일때 
	
	cout<<min(on, off);
	return 0;
}

devbelly 3년 전 0

visited 배열이 재방문을 막는코드가 어디인가요?

ryu_eclipse 3년 전 0

아 소스코드 옮기면서 주석 지우다가 그것까지 지웠네요...

17번줄에 if(visited[next]) continue; 넣어도안됩니다 ㅠㅠ

devbelly 3년 전 0

음 두번째 dfs(1,1)을 할때 visited를 초기화 해야하지 않나요?

ryu_eclipse 3년 전 0

그부분도 좀전에 고려해서 해봤는데 여전히 안되더라고요 ㅠㅠ

아무래도 재귀함수를 잘못짠 것같아서

이번에는, dfs함수를 void 형식으로 했는데 되긴 됐어요..

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int> > vec, dag;
int visited[1000000+5];
int dp[1000000+5][2];
int n, a,b;


void dfs(int node){
//	int flag=0;
	visited[node] = 1;
	
//	if(dp[node][early]!=-1) return dp[node][early]; 
	dp[node][1]= 1;//자기자신 추가 
	
	for(int i=0;i<vec[node].size();i++){
		int next = vec[node][i];
		if(visited[next]) continue;
		//flag=1;
		
		dfs(next);
		dp[node][0] += dp[next][1];
		
		dp[node][1] += min(dp[next][0], dp[next][1]); 
	}
	//if(flag==0) 
	
	
	//return dp[node][early];
}

int main(){
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	cin>>n;
	vec.resize(n+1);
	dag.resize(n+1);
	for(int i=0;i<n-1;i++){
		cin>>a>>b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
//	mk_dag(1); //DAG 생성 
//	for(int i=0;i<=n;i++) dp[i][0] = dp[i][1] = -1;
//	int off = dfs(1); //루트가 얼리어댑터가 아닐때 
//	fill(visited, visited+n+2, 0);
//	for(int i=0;i<=n+1;i++) dp[i][0] = dp[i][1] = 0;
	dfs(1);	
	int off = dp[1][0];
	int on = dp[1][1]; //루트가 얼리 어댑터 일때 
//	printf("%d %d", off, on);
	
	cout<<min(on, off);
	return 0;
}

ryu_eclipse 3년 전 0

근데 이건 맞고, 아까건 왜틀렸는지..찜찜하네요

devbelly 3년 전 0

그리고 dfs 내부에서

if 내가 early

내주변을 확인하는 for문~

else

내 주변을 확인하는 for문~ 이어야 할 것 같아요

devbelly 3년 전 0

수정하신 코드는 루트에서 리프까지 다 찾은다음에 (22번쨰줄에서 재귀로 다 찾음) 리프에서부터 쌓아올라가는 바텀업 비슷한 느낌같아용

ryu_eclipse 3년 전 1

어렵네요...내일 일어나서 다시 생각해봐야겠습니다

답변 계속 달아주셔서 감사합니다

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

문제

문제

출처

ICPC

왜 안되는지 모르겠습니다...

ryu_eclipse 3년 전 0

devbelly 3년 전 0

ryu_eclipse 3년 전 0

devbelly 3년 전 0

ryu_eclipse 3년 전 0

ryu_eclipse 3년 전 0

devbelly 3년 전 0

devbelly 3년 전 0

ryu_eclipse 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말