BOJ 11725 - 트리의 부모 찾기

문제 링크

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

풀이

루트가 1번으로 고정된 트리이므로, 1번에서 한 번만 탐색하면서 처음 내려가는 간선을 부모-자식 관계로 기록하면 된다. 현재 코드는 인접 리스트를 따라가며 아직 방문하지 않은 정점에 대해 부모 번호를 저장한다.

트리는 사이클이 없어서 한 번 정한 부모가 다시 바뀌지 않는다. 결국 핵심은 1번에서 출발해 방문 순서를 정하고, 직전에 있던 정점을 부모로 남기는 것이다.

코드

#include <iostream>
#include <vector>
using namespace std;
 
const int MAX = 100000;
vector<int> vec[MAX + 1];
bool visited[MAX + 1];
int parent[MAX + 1];
 
void dfs(int node) {
	visited[node] = true;
 
	for (int i = 0; i < vec[node].size(); i++) {
		
		int num = vec[node][i];
 
		if (!visited[num]) {
			parent[num] = node;
			dfs(num);
		}
	}
}
 
void solve() {
 
	int n;
	cin >> n;
 
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
 
	dfs(1);
 
	for (int i = 2; i <= n; i++) 
		cout << parent[i] << '\n';
}	
 
int main() {
    
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    
	solve();
 
    return 0;
}

복잡도

시간 복잡도: 트리의 모든 정점과 간선을 한 번씩 탐색하므로 $O(N)$ 이다.
공간 복잡도: 인접 리스트와 부모 배열을 저장하므로 $O(N)$ 이다.

마무리

루트에서 한 번 내려가며 처음 만난 방향을 부모 관계로 확정하는 문제다. 트리에서는 경로가 하나뿐이라 DFS가 기록한 부모가 그대로 정답이 된다.

문제#

입력#

출력#

풀이#

코드#

복잡도#

마무리#

문제

입력

출력

풀이

코드

복잡도

마무리