[백준 / BOJ] 11725번 : 트리의 부모 찾기 (C++)

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

11725번: 트리의 부모 찾기

 이번 문제는 트리의 간선을 입력으로 받고 2부터 마지막 노드까지의 부모 노드를 출력하는 문제입니다.

 

 트리도 그래프의 일종이므로 저는 BFS를 써서 문제를 풀었습니다. 트리의 루트 노드는 1이므로 1을 시작으로 BFS를 돌리면서 노드를 방문할 때 이전 노드의 값을 답으로 저장하면 됩니다. DFS로도 가능합니다.

 

 아래는 제 코드입니다.

 

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int n;
vector<int>adj[100002];
bool visited[100002];

void bfs() {
	queue<int>q;
	vector<int>ans(n + 1);
	q.push(1); //루트노드 1에서 시작

	while (!q.empty()) {
		int nowNode = q.front();
		visited[nowNode] = true;
		q.pop();

		//각 노드의 다음 노드를 방문
		for (auto i : adj[nowNode]) {
			if (!visited[i]) {
				ans[i] = nowNode; //다음 노드의 부모는 현재 노드
				q.push(i);
			}
		}
	}

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

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

	bfs();
	
	return 0;
}