백준 11725번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초	256MB	실버 2

---

풀이

이 문제의 풀이를 사용하는 알고리즘 문제를 공부하고 풀어본 적이 있어서 쉽게 푼 것 같다. LCA라는 알고리즘인데, 이 알고리즘을 사용하는 문제도 역시 블로그 글 쓰기에 밀려있는 문제들이다. 조만간 풀이하겠다.

 

 언뜻 보면 어려워보일수 있다. 입력의 각 줄의 데이터가 가 부모-자식 순서라는 보장이 전혀 없기 때문이다. 정말 정점간 연결 정보만을 알려주기 때문이다. 트리는 아주 특수한 형태의 그래프이다. 트리는 계층 구조를 가지는 자료구조이지만, 동시에 사이클, 즉 순환이 없는 그래프이기도 하다. 이런 그래프는 어떤 정점을 고르더라도 트리가 될 수 있다. 순환 구조가 없기 때문에, 정리하다보면 계층구조가 만들어지기 때문이다.

 

 입력받은 정점간 연결 정보를 맨 처음에 양방향 그래프로 작성한 후, 루트 노드를 1번으로 가정하기 때문에 1에서부터 dfs로 탐색하면서 부모의 정보도 같이 넘겨주면 dfs로 탐색하여 들어온 노드에서 부모의 정보를 바로 알 수 있을 것이다. 이를 통해 부모 노드의 정보를 저장해나가면 문제는 해결된다.

코드

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int n;
vector<vector<int>> graph;
vector<int> parent;

void input() {
	int a, b, cnt;
	cin >> n;
	cnt = n;
	graph.resize(n + 1);
	parent.resize(n + 1, -1);
	while(--cnt){
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
}
void dfs(int prev, int cur) {
	parent[cur] = prev;

	for(int nxt : graph[cur]) {
		if (nxt == prev) continue;
		dfs(cur, nxt);
	}
}

void sol() {
	dfs(-1, 1);
	for(int i = 2; i <= n; i++) {
		cout << parent[i] << endl;
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	input();
	sol();
}