백준 11725 트리의 부모 찾기 c++ (dfs)

문제 출처 : https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

문제

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

입력

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

출력

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

 

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 트리
• 너비 우선 탐색
• 깊이 우선 탐색

풀이

주어진 노드들이 부모-자식 관계로 주어진 것이 아니니 양방향 그래프로 인접 리스트 그래프를 만들어야 한다.

이후 루트는 항상 1번 노드이니 1번 노드에서부터 dfs 탐색을 시작하여,

간선을 통한 다음 노드의 부모 노드는 현재 노드가 된다.

 

코드

#include <iostream>
#include <vector>

using namespace std;
int n;
vector<int> graph[100001];
int parent[100001];

void dfs(int node) {
	
	for (int i = 0; i < graph[node].size(); i++) {
		int next = graph[node][i];
		if (parent[next] == 0) {
			parent[next] = node;
			dfs(next);
		}
	}
	
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int from, to;
		cin >> from >> to;
		//양방향그래프
		graph[from].push_back(to);
		graph[to].push_back(from);
	}

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

	return 0;
}