백준 1991번: 트리 순회 (C++)

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

풀이방법

해당 문제는 트리 탐색 방법 중에서 재귀를 활용한 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)를 코드로 구현하는 방법을 물어보는 문제다. 순회에 대한 3가지 개념을 이론적으로만 알고 있어도 특별히 어려움은 없으나, 문자열을 숫자로 변환해서 생각 하는게 조금, 아주조금 헷갈릴 수 있는 문제다. 허나 A=1이라는 가정하고 문제를 풀면 굉장히 쉽게 풀 수 있다. 해설 풀이는 아래와 같다.

코드

#include <bits/stdc++.h>
using namespace std;


int p[100'005];
vector<int> adj[100'005];
int n;

void dfs(int cur)
{
	for (auto nxt : adj[cur])
	{
		if (p[cur] == nxt) continue;
		p[nxt] = cur;
		dfs(nxt);
	}
}

int main()
{
	cin >> n;
	for (int i = 0; i < n - 1; i++)
	{
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1);

	for (int i = 2; i <= n; i++)
	{
		cout << p[i] << '\n';
	}

}