[백준] 11725번. 트리의 부모 찾기

[백준] 11725번. 트리의 부모 찾기

1. 문제

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

2. 입력

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

3. 출력

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

4. 풀이

• BFS를 이용했다.
• 루트는 항상 1이기 때문에 1을 기준으로 BFS를 하였고 현재까지 방문 하지 않은 노드 중 현재 단계에서 연결된 노드는 현재 단계 노드의 자식노드가 된다. parent배열에 자식 인덱스에 부모 노드를 기록하고 출력해주었다.

5. 처음 코드와 달라진 점

• 간선의 개수를 잘못 생각해서 n-1을 n으로 썼다.
• 방문 표시를 안 해주어서 수정했다.

6. 코드

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

using namespace std;

vector<int> graph[100001];
bool visited[100001];
int parent[100001];
int n;

void bfs() {
	queue<int> q;
	q.push(1);
	visited[1] = true;

	while (!q.empty()){
		int x = q.front();
		q.pop();

		for (int i = 0; i < graph[x].size(); i++){
			int y = graph[x][i];
			if (!visited[y]) {
				q.push(y);
				visited[y] = true;
				parent[y] = x;
			}
		}
	}
}

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

	cin >> n;

	for (int i = 0; i < n-1; i++){
		int node1, node2;
		cin >> node1 >> node2;
		graph[node1].push_back(node2);
		graph[node2].push_back(node1);
	}

	bfs();

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