BOJ 11725 - 트리의 부모 찾기

• 간선 정보와 루트의 번호만 주어질 때 각 노드들의 부모를 출력하는 문제이다.

문제 풀이

• 루트노드에서부터 자식들을 bfs로 탐색하면서 부모를 찾아내었다.

• 아래 코드에서 주석들은 풀고나서 다른 사람들의 코드를 보면서 공부한 것으로, 밑에서 설명하겠다.

소스코드

#include<cstdio>
#include<vector>
#include<deque>
#include<utility>
using namespace std;
typedef pair<int, int> pii;

int main()
{
	int n;
	scanf("%d", &n);
	vector<int> p(n+1, 0);
	p[1]=1;
	deque<pii> d;
	for(int i=0;i<n-1;i++){
		int a, b;
		scanf("%d %d", &a, &b);
		if(p[a]) p[b]=a;
		else if(p[b]) p[a]=b;
		else d.push_back({a, b});
	}
	
	// while(!d.empty()){		//TLE
	// 	deque<pii> d2;
	// 	d2.swap(d);
	// 	for(int i=0;i<d2.size();i++){
	// 		int a=d2[i].first, b=d2[i].second;
	// 		if(p[a]) p[b]=a;
	// 		else if(p[b]) p[a]=b;
	// 		else d.push_back({a, b});
	// 	}
	// }
	while(!d.empty()){		//40ms
        deque<pii> r;
        r.swap(d);
        while(!r.empty()){
            int a=r.front().first,b=r.front().second;r.pop_front();
            if(p[a])p[b]=a;
            else if(p[b])p[a]=b;
            else d.push_front({a,b});
        }
    }
	
	for(int i=2;i<=n;i++) printf("%d\n", p[i]);
	return 0;
}

// #include<cstdio>
// #include<vector>
// #include<queue>
// #include<algorithm>
// #include<utility>
// using namespace std;
// typedef vector<int> vi;
// typedef pair<int, int> pii;

// int main()
// {
// 	int n;
// 	scanf("%d", &n);
// 	vi p(n+1), v(n+1, 0);
// 	vector<pii> e;
// 	for(int i=1;i<n;i++){
// 		int s, z;
// 		scanf("%d %d", &s, &z);
// 		e.push_back(make_pair(s, z));
// 		e.push_back(make_pair(z, s));
// 	}
// 	sort(e.begin(), e.end());
// 	queue<int> q;
// 	auto lb=lower_bound(e.begin(), e.end(), make_pair(1, 1)), ub=upper_bound(e.begin(), e.end(), make_pair(1, n));
// 	v[1]=1;
// 	for(auto it=lb;it!=ub;++it){
// 		p[it->second]=it->first;
// 		q.push(it->second);
// 		v[it->second]=1;
// 	}
// 	while(!q.empty()){
// 		int cur=q.front(), f=1;
// 		lb=lower_bound(e.begin(), e.end(), make_pair(cur, 1)), ub=upper_bound(e.begin(), e.end(), make_pair(cur, n));
// 		for(auto it=lb;it!=ub;++it){
// 			if(v[it->second]==0){
// 				p[it->second]=it->first;
// 				q.push(it->second);
// 				f=0;
// 				v[it->second]=1;
// 			}
// 		}
// 		if(f) q.pop();
// 	}
// 	for(int i=2;i<=n;i++) printf("%d\n", p[i]);
// 	return 0;
// }

풀고나서

• 내가 처음 제출한 코드는 맨아래 전부 주석처리된 부분으로, 위의 문제 풀이대로 푼 것이다. 풀고나서 isbidip님의 코드를 봤는데 나보다 훨씬 깔끔하고 시간도 적게 들어서 이해한대로 다시 코딩해서 제출했다. 근데 TLE가 떴었다. 보이는 차이는 deque에서 push_front와 push_back의 차이밖에 없었기 때문에 질문을 올렸고, 이건 저 함수들의 실행시간 차이가 아니라 deque가 뒤집히냐 아니냐의 차이였다. TC중에 일자 트리에서 간선이 양끝에서부터 번갈아가며 주어지는 테스트케이스가 많았나보다. 어쨌든 따지고보면 둘 다 O(N^2)이기 떄문에 원래는 TLE가 나야해서 데이터 추가가 요청되었고 현재 내 맨 처음 코드와 두 번째 코드는 재채점 중이다. 첫 번째는 O(NlgN)이기 때문에 맞을거고 두 번째는 아마 틀렸다고 뜰 것 같다.

• 루트가 주어지기 때문에 루트에서 dfs만 돌려도 다 구할 수 있다. 괜히 어렵게 생각했다. (djm03178님의 코드를 보고 깨달음을 얻었다.)

• 코드는 깔끔한 게 최고인 것 같다. 앞으로 bits/stdc++.h헤더하고 iostream을 사용해야겠다.