백준 11725: 트리의 부모 찾기

문제 요약

각 정점이 연결된 간선의 형태가 주어지면, 해당 형태로 하여금 그래프를 트리로 파악하여 각 정점의 부모 노드 번호를 각 줄마다 출력한다.

문제 분류

• 그래프 이론
• 그래프 탐색
• 트리
• DFS
• BFS

문제 풀이

정점의 루트 번호가 1이라고 했으니, 1에서 부터 BFS를 해나가면 된다.

큐의 원소는 pair<int,int>로, 첫번째 값은 현재 탐색 중인 정점의 번호이고, 두 번째 값은 해당 정점의 부모 노드이다.
즉, 현재 1인 정점을 탐색하고 있다면, 1의 자식들을 BFS하면 그들의 부모 노드는 1이 될 것이다. 이런 식으로 각 정점들을 BFS로 방문하며 자식들의 부모 노드를 찾아갔다.

마지막으로 res배열을 정의하여 각 인덱스별로 부모의 정점 번호를 대입해서 for문으로 출력하기로 했다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;

multimap<int, int> m;
bool visited[100001] = { false };
int res[100001] = { 0 };

int main()
{
	int n, in, in2;
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		scanf("%d%d", &in, &in2);
		m.insert({ in, in2 });
		m.insert({ in2, in });
	}
	queue<pair<int, int>> q;

	q.push({1,0});
	while (!q.empty()) {
		auto t = q.front().first;
		res[t] = q.front().second;
		q.pop();

		auto range = m.equal_range(t);
		for (auto& it = range.first; it != range.second; it++) {
			if (!visited[it->second]) {
				visited[it->second] = true;
				q.push({ it->second, t });
			}
		}
	}
	for (int i = 2; i <= n; i++)
		printf("%d\n", res[i]);
	return 0;
}

후일담

알고리즘이 DFS로도 분류되어 있는데,DFS로도 풀어보면 좋을 것 같다.