[백준] 11725 트리의 부모 찾기 - C++

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

---

트리의 부모를 찾아주면 된다..

이진트리가 아니라는 점에서 이전 포스트에서 사용했던 방식인 pair형 vector는 쓰기 어렵다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<vector<int>> graph(100'001);
int visited[100'001];
void dfs(int cur) {
	for (int next : graph[cur]) {
		if (!visited[next]) {
			visited[next] = cur;
			dfs(next);
		}
	}
}
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int u,v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	dfs(1);
	for (int i = 2; i <= n; i++) {
		cout << visited[i] << "\n";
	}
	return 0;
}

 

노드 간 부모자식관계를 정해주면 된다.

 

graph는 해당 인덱스번째 노드와 인접한 노드들을 저장하는 vector형 vector이다.

main함수에서는 주어지는 인접한 노드들을 저장해 준다.

 

이후에 dfs함수를 실행하는데, 문제에서 1번 노드가 루트라고 했으니 1을 넣어 실행한다.

dfs함수는 인자로 넘어온 현재노드와 연결된 노드를 탐색하는데,

이때 부모가 정해지지 않은 노드와 연결되어 있다면 현재 노드를 부모노드로 정하고 해당 노드를 탐색한다.

이러한 과정을 거치면 visited배열에는 해당 인덱스번째 노드의 부모가 값으로 들어가게 된다.

 

2번 노드부터 n번노드까지 해당 노드의 부모를 출력해 주면 되므로,

for문을 돌며 visited 배열의 값을 꺼내온다.

---

 

문제 조건을 안 읽고 입력값의 왼쪽이 부모고 오른쪽이 자식인 줄 알고

상당한 뻘짓을 했었다.. 문제 조건을 잘 읽도록 하자.

---