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

 

문제 11725번

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

 

이번에는 그래프에 관한 문제를 풀어보려고 한다.

 

첫째 줄에 노드의 개수 n이 주어지고 둘째 줄부터 n-1개의 줄에 트리 상에서 연결된 두 정점이 주어지기 때문에 입력받고 벡터에 넣어줄 때 반복문을 0부터 n-2까지 반복할 수 있도록 해준다(예를 들어 7을 입력받으면 6번 반복해줌). 이때 양방향으로 연결되어 있으니까 반대인 경우도 벡터에 넣어줘야한다.

 

깊이 우선 탐색(dfs)을 이용하여 그래프를 탐색할 것이다. 깊이 우선 탐색이란 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 된다면 다시 가장 가까운 갈림길로 돌아와서 해당 위치부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다. 즉, 하나의 방향으로 최대한 깊이 들어갔다가 다시 돌아와 다른 루트로 탐색하는 것이다.

 

트리의 루트를 1이라고 정했으니 1부터 시작하여 dfs를 수행한다. 해당 노드는 방문했다는 표시를 하기 위해 true로 바꿔주고 그 노드와 연결되어 있는 다른 노드의 개수만큼 반복문을 사용한다. 해당 노드의 다음을 next에 넣고 인덱스로 이용하여 방문한 노드인지 확인하고 아직 방문하지 않은 노드인 경우에는 next 노드의 부모를 node로 넣어준다. 그리고 next 노드를 다시 dfs 해준다. 그렇게 탐색을 마치면 2번 노드의 부모부터 순서대로 출력해준다.

 

#include <iostream>
#include <vector>
using namespace std;

const int MAX = 100001;
vector<int> tree[MAX];
bool visited[MAX];
int parent[MAX];

void dfs(int node) {
	visited[node] = true;
	for (int i = 0; i < tree[node].size(); i++) {
		int next = tree[node][i];	//해당 노드의 다음
		if (!visited[next]) {	//아직 방문하지 않은 노드인 경우
			parent[next] = node;
			dfs(next);
		}
	}
}

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int x, y;
		cin >> x >> y;
		tree[x].push_back(y);	//양방향
		tree[y].push_back(x);
	}

	dfs(1);	//트리의 루트 1

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

	return 0;
}