[백준 C++] 11725 트리의 부모 찾기 - 너비우선탐색

11725번: 트리의 부모 찾기

#include <iostream>
#include <list>
#include <queue>
using namespace std;

int N;
int Parent[100001];
bool Visited[100001];
list<int> Neighbors[100001];
queue<int> SearchQueue;

void BFS(int Root)
{
	SearchQueue.emplace(Root);
	while (!SearchQueue.empty())
	{
		int Current = SearchQueue.front();
		SearchQueue.pop();

		if (Visited[Current])
		{
			continue;
		}

		Visited[Current] = true;
		for (const int& Neighbor : Neighbors[Current])
		{
			if (!Visited[Neighbor])
			{
				Parent[Neighbor] = Current;
				SearchQueue.emplace(Neighbor);
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;
	for (int i = 0; i < N - 1; ++i)
	{
		int A, B;
		cin >> A >> B;
		Neighbors[A].emplace_back(B);
		Neighbors[B].emplace_back(A);
	}

	BFS(1);
	for (int i = 2; i <= N; ++i)
	{
		cout << Parent[i] << '\n';
	}
}

---

 

주어진 그래프에서 각 노드의 부모 노드를 찾는 문제로 BFS 알고리즘을 사용해서 풀었습니다.

풀이 과정은 다음과 같습니다.

 

1. 각 노드의 연결 정보를 인접 리스트에 저장

2. 루트 노드(1번) 부터 너비 우선 탐색 시작

3. 현재 노드의 미방문 인접 노드의 부모 정보를 현재 노드로 저장 & 해당 인접 노드 큐에 추가

4. 3번 반복

5. 저장된 부모 정보 배열 출력