[ BOJ 백준 11725번 - 트리의 부모 찾기 ] 해설 및 코드

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

 

 

목적

노드의 쌍이 주어질 때, 부모를 찾아내자.

 

접근법

1. 노드의 쌍을 입력 받을 때마다, 부모를 알아낼 수 있다면, 즉, 노드 쌍 중의 하나의 부모가 정해진 경우라면, 나머지 노드의 부모를 결정한다.

 

2. 그렇지 않은 경우 큐에 넣어서 남은 쌍의 부모를 찾아나가는데, 큐에 넣는다면 최악의 경우에 큐의 맨 뒤에 있는 쌍만 처리될 수 있다. 그렇다면 O(N^2)의 시간복잡도가 걸리게 되므로, deque 자료구조를 이용해서 순서를 번갈아가면서 처리해 준다. 

 

3. 다른 접근법으로 노드의 쌍을 입력받아 저장한 뒤에 DFS로 부모를 결정할 수도 있는데, O(N)의 시간복잡도로 AC를 받을 수는 있으나, 메모리가 과도하게 많이 필요하다.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;i++)
#define LEN 100001
using namespace std;
 
struct Pair{int a,b;};
int n,p[LEN]{0,1};
 
int main(){
    ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    
    deque<Pair> q;
    cin>>n;
    f(i,2,n){
        int a,b;cin>>a>>b;
        if(p[a])p[b]=a;
        else if(p[b])p[a]=b;
        else q.push_back({a,b});
    }
    
    while(!q.empty()){
        deque<Pair> r;
        r.swap(q);
        while(!r.empty()){
            int a=r.front().a,b=r.front().b;r.pop_front();
            if(p[a])p[b]=a;
            else if(p[b])p[a]=b;
            else q.push_front({a,b});
        }
    }
    
    f(i,2,n)cout<<p[i]<<'\n';
    return 0;
}
 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.