백준 2233 사과나무

https://www.acmicpc.net/problem/2233

트리에서 가지를 잘라내면서 떨어지는 과일을 최소로 한다는 의미는 LCA를 찾으라는 말과 동치입니다. 하지만 쿼리 문제는 아니기 때문에 O(n)의 방식으로 LCA를 구하겠습니다.

dfs했던 결과에서 parent 정보를 뽑아내기 위해서는 스택을 사용하면 편리합니다.(dfs가 스택을 이용하는 탐색이기 때문입니다.)

0: 스택에 새로운 노드를 추가. 스택에 위에 있었던 노드가 추가되는 노드의 부모

1: 스택에서 뽑아냄

나머지는 구현입니다.

#include<bits/stdc++.h>
using namespace std;
const int SZ=2005;
int par[2*SZ];
int one[2*SZ];
int zero[2*SZ];
int level[2*SZ];
string tree;
int level_up(int x, int d){
	for(int i=0;i<d;i++) x=par[x];
	return x;
}
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	int n; cin>>n;
	cin>>tree;
	stack<int> s; int p=0, idx=0;
	s.push(p++);
	for(char x:tree){
		idx++;
		if(x=='0'){
			int t=s.top();
			par[p]=t;
			level[p]=level[t]+1;
			zero[idx]=p;
			s.push(p++);
		}
		else{
			one[idx]=s.top();
			s.pop();
		}
	}
	int x,y; cin>>x>>y;
	if(tree[x-1]=='0') x=zero[x];
	else x=one[x];
	if(tree[y-1]=='0') y=zero[y];
	else y=one[y];
	x=level_up(x,max(0,level[x]-level[y]));
	y=level_up(y,max(0,level[y]-level[x]));
	while(x!=y){
		x=par[x];
		y=par[y];
	}
	for(int i=1;i<=2*n;i++){
		if(zero[i]==x){
			cout<<i<<" ";
			break;
		}
	}
	for(int i=1;i<=2*n;i++){
		if(one[i]==x){
			cout<<i;
			break;
		}
	}
	return 0;
}