[백준문제풀이] 11725 트리의 부모 찾기

 

풀이 일시 : 2020-12-27

 

 

문제 : 

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

 

 

입력 : 

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

ex)

7

1 6

6 3

3 5

4 1

2 4

4 7

 

 

출력 : 

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

ex)

4

6

1

3

1

4

 

 

풀이 : 

입력이 주어지는 것을 vector에 받아 트리를 구성해준다.

 

BFS로 모든 노드를 탐색하며 각각 노드마다 자신의 부모를 체크해줄 수 있다.

 

자신의 부모를 체크했다면 parent 배열에 저장해주고 한번에 출력해주자.

 

//트리의 부모찾기
//입력에서 두 정점이 연결되었다는것은 하나는 그것의 부모이고 하나는 자식일것이다.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAX = 100001;
int N;
vector <int> v[MAX];
int visited[MAX];
int parent[MAX];

void bfs() { //모든 노드를 탐색하며 그때그때 자신의 부모를 체크한다.
	queue<int>q;
	q.push(1); //1이 루트라고 설정해놓음
	visited[1] = 1;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = 0; i < v[x].size(); i++) {
			int z = v[x][i];
			if (!visited[z]) {
				parent[z] = x; //check parent
				visited[z] = 1;
				q.push(z);
			}
		}
	}
}
void printparent() {
	for (int i = 2; i <= N; i++) {
		cout << parent[i] << '\n';
	}
}

int main() {
	cin >> N;
	int val1,val2;
	for (int i = 0; i < N-1; i++) {
		cin >> val1>>val2;
		v[val1].push_back(val2);
		v[val2].push_back(val1);
	}
	bfs();
	printparent();

	return 0;
}

 

참고자료 : vector

dbstndi6316.tistory.com/25

[개념정리] vector container

참고자료 : BFS

dbstndi6316.tistory.com/63

[기본문제풀이] BFS 너비우선탐색