[백준] 13306번: 트리

 

---

문제링크: [백준] 13306번 트리

13306번: 트리

1. 문제 요약

트리구조에서 부모정점에 대한 정보와 연결경로를 묻는 문제인데요. 집합의 대표요소와 부모정점 비슷한 말 같지않나요? 저번 자료구조 포스팅에서 다뤘던 디스조인트 자료구조와 유니온 파인드 연산을 이용하여 푸는 문제였습니다. 

N개의 정점이 숫자 1부터 N까지로 표현되고 루트는 항상 1입니다. 트리의 정점 개수 N, 질의의 개수 Q가 주어지고 2번정점 부터 N번 정점까지 부모정점을 나타내는 정수 a가 주어집니다. 그리고 (N-1)+Q 줄 에서 두 가지 형태의 입력이 주어지는데 첫 번째는 경로삭제이고 두 번째는 두 정점간에 경로가 존재하는지 묻는 질의입니다.

---

2. 문제 풀이 및 코드

출력부를 보면 질의에 대한 답을 순서대로 Q개의 줄에 YES or No 로출력한다고 합니다. 그렇기 때문에 N-1+Q 줄 간에 들어오는 모든 입력을 스택구조에 순차적으로 저장하면서 경로를 삭제하는 입력인 경우에  미리 경로를 삭제했습니다. 그 과정이 끝나면 스택에서 마지막 질의에 대한 답부터 Find 연산을 통해 대표요소를 확인하고(연결 여부 확인) 답을 ans 스택에 집어 넣었습니다. 그리고 삭제 입력이 들어왔던 차례가 오면 부모와 자식노드를 Union 연산을 통해 다시 연결시켜주었습니다. 마지막으로 ans 스택을 출력함으로서 문제를 풀 수 있었습니다.

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,pair<int,int>> ipii;
const int MAX = 200000 + 1;
int N,Q,par[MAX];
stack<ipii> qList;
stack<string> ans;

// Find 연산
int doFind(int x){				
	if(x==par[x]) return x;
	return par[x]=doFind(par[x]);
}

// Union 연산
void doUnion(int a, int b){			
	a=doFind(a);
	b=doFind(b);
	if(a==b) return;
	par[a]=b;
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>N>>Q;
	for(int i=1;i<=N-1;i++){
		int parNode;
		cin>>parNode;
		par[i+1]=parNode;
	}
	int cnt=N-1+Q;
	while(cnt--){
		int x,b,c,d;
		cin>>x;
		if(!x) {
			cin>>b;
            
            	// 경로 삭제: first: 0 second: {자식,부모}
			qList.push({0,{b,par[b]}});	
            
            	// 경로 삭제: 부모 == 자기 자신
			par[b]=b;		   	
		}
		else{
			cin>>c>>d;
            
            	// 질의 first: 1 second: {c,d}
			qList.push({1,{c,d}});		
		}
	}
	while(!qList.empty()){
    
    		// 질의
		if(qList.top().first){			
			int c=qList.top().second.first;
			int d=qList.top().second.second;
            
            	// Find연산를 통해 연결 확인
			if(doFind(c)==doFind(d)) ans.push("YES");	
			else ans.push("NO");
		}
        
       		// 경로 삭제: Union연산을 통해 다시 연결
		else{							
			int par=qList.top().second.second;	
			int child=qList.top().second.first;
			doUnion(child,par);
		}
		qList.pop();
	}

	while(!ans.empty()){
		cout<<ans.top()<<"\n";
		ans.pop();
	}
	return 0;
}

---

3. 마무리

더 좋은 풀이나 부족한 부분 언제든지 지적과 조언 감사합니다!