[ boj : 14678 ] 어그로 끌린 영선

www.acmicpc.net/problem/14678

14678번: 어그로 끌린 영선

문제 : 트리가 주어지고 영선이는 아무 정점에서 '왼발'부터 시작합니다. 이때 다른 한쪽발을 번가라가면서 한칸씩 이동할 수 있고 더이상 갈 곳이 없을때 '왼발'을 디딤고 있으면 영선이가 이깁니다. 영선이가 이길 수 있는 경우의 수를 구하시오

 

해설 : 단순히 모든 정점에서 DFS를 실행하여 나오는 경우의 수를 전부 구하면 되지 않냐? 라고 생각할 수도 있지만 정점의 최대 개수는 1,000,000 이니 절대 해결할 수 없다는 것을 파악할 수 있습니다.

그럼 다른 방법을 생각해 봐야 하는데 이런 문제 유형의 접근 방법은 '정량화'되어 있다고 합니다.

흔히 '트리디피' 문제라고 하네요.

 

먼저 리프노드가 될 수 있는 정점을 제외한 정점들 중 아무 정점에서 DFS를 실행합니다.

(왜 리프노드가 되는 정점은 안되는지는 후에 설명하겠습니다)

이때 DFS를 실행하는데 상태값을 저장해 주면서 실행합니다. 즉, 각 정점에서 리프노드까지 거리(홀,짝)의 개수를 저장해주는 것입니다. 그럼 현재 정점의 정보를 저장해 주고 부모노드로 리턴될때는 (홀,짝)의 개수가 (짝,홀)의 개수로 뒤바꾸어 저장을 하게 되는 것이죠.(이건 따로 왜 이렇게 되는지 설명은 안하고 직접 펜과 종이로 그려보세요)

 

그럼 우린 일단 첫번째 DFS를 통해 '자식'노드들의 정보들을 알 수 있습니다. 그러나 이 정보들은 반쪽짜리 정보입니다. 이유는 현재 정점에서 첫번째 DFS를 돌릴때 선정한 root 노드의 기준에서만 정보들을 얻어왔기 때문이죠.

남은 정보는? 현재 정점이 root 노드가 되었을때의 정보들을 얻어오면 끝입니다. 

그런데 가만히 생각해 보면 현재 정점이 root 노드가 되었을때 정보들은 결국 첫번째 DFS를 돌렸을때 root 노드가 가지고 있는 정보와 같게 됩니다.

그 이유는 root 노드가 가지고 있는 정보들의 '값'들은 변함이 없고 단순히 (홀,짝)인지 (짝,홀) 인지만 달라지게 되기 때문이죠.

 

다만 조심해야 될 부분은 만약 리프노드에 도달을 하였을때는 그 리프노드가 root가 되었을때 (홀,짝)의 개수 중 하나가 빠지게 되는데 무조건 짝수개만 빠지게 됩니다. 왜 짝수개냐면 에초에 리프노드가 리턴시켜줄땐 '홀수'로 넘겨주기 때문입니다. 그래서 위에서 첫번째 DFS를 실행할때 리프노드가 될 수 있는 노드를 제외하고 탐색해주는 것 입니다.

 

#include<bits/stdc++.h>

using namespace std;

const int SIZE = (int)1e6 + 1;

struct info {
	int odd, even;
}A[SIZE];

bool visit[SIZE];
int root;
vector<int> v[SIZE];

void solve();
info dfs1(int x, int p);
void dfs2(int x, int p, int s, int e);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	solve();
	return 0;
}
void solve()
{
	int n;
	cin >> n;
	if (n == 1) {
		cout << 1;
		return;
	}
	int x, y;
	for (int i = 0; i < n - 1; i++) {
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for (int i = 1; i <= n; i++)
		if (v[i].size() > 1) {
			root = i;
			break;
		}
	dfs1(root, -1);
	memset(visit, 0, sizeof(visit));
	dfs2(root, -1, A[root].odd, A[root].even);
	int ans = 0;
	for (int i = 1; i <= n; i++)
		ans = max(ans, A[i].even);
	cout << ans;
}
info dfs1(int x, int p)
{
	if (visit[x])return{ 0,0 };
	visit[x] = true;

	for (int i = 0; i < v[x].size(); i++) {
		if (p == v[x][i])continue;		
		info ret = dfs1(v[x][i], x);
		A[x].odd += ret.even;
		A[x].even += ret.odd;
	}
	//leaf node
	if (A[x].odd + A[x].even <=0) 
		return { A[x].odd,A[x].even + 1 };
	else 
		return A[x];
}
void dfs2(int x, int p, int s, int e)
{
	if (visit[x])return;
	visit[x] = true;

	bool inner = false;
	for (int i = 0; i < v[x].size(); i++) {
		if (p == v[x][i])continue;
		dfs2(v[x][i], x, e, s);
		inner = true;
	}
	if (!inner) {
		A[x].odd = s;
		A[x].even = e - 1;
	}
	else if(root!=x){
		A[x].odd = e;
		A[x].even = s;
	}
	return;
}