C++ / 백준 / 11725 / 트리의 부모 찾기

문제

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

11725번: 트리의 부모 찾기

문제풀이

BFS를 이용하여 풀었다.

1 2를 입력받으면 양방향 간선이므로 tree[1]에 2를 push, tree[2]에 1을 push 했다.

큐가 빌 때까지 반복하면서 해당 정점과 연결된 정점들을 방문한 적이 없으면 큐에 push 하고 방문한다.

현재 노드가 1이고 다음 노드가 2이면, 2의 부모 노드는 1이 된다.

큐가 비면 반복문을 종료하고 1을 제외한 2부터 N까지 부모 노드를 저장한 벡터의 값들을 출력한다.

 

	vector<vector<int>>tree(N + 1, vector<int>(0, 0));
	vector<int>parents(N + 1, 0);
	vector<bool>visit(N + 1, false);

tree는 트리 구조에 관련된 벡터, 정점 개수+1만큼 행을 만들고, 빈 열을 만들고 입력받을 때마다 push 하여 늘린다.

parents는 부모 노드를 저장하는 벡터로, parents[index]는 index의 부모 노드 값을 저장한다.

visit은 방문 표시를 하는 벡터이다.

 

	int num = 1;

	queue<int>q;
	q.push(1);

	while (!q.empty()) {
		visit[num] = true;
		num = q.front();
		q.pop();
		for (int cnt = 0; cnt < tree[num].size(); ++cnt) {
			if (!visit[tree[num][cnt]]) {
				parents[tree[num][cnt]] = num;
				q.push(tree[num][cnt]);
			}
		}
	}

문제에서 트리의 루트는 1이라고 나와있으므로, 1부터 시작하고 큐에 push를 한다.

BFS이므로 벡터 크기만큼 돌면서 방문한 적 없는 연결된 노드들을 모두 방문, push 한다.

push 한 노드들의 부모 노드는 현재 노드 num이기 때문에 parents벡터에 저장한다.

 

코드

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int y = 0;
	int N = 0;
	int num1 = 0, num2 = 0;
	cin >> N;

	vector<vector<int>>tree(N + 1, vector<int>(0, 0));
	vector<int>parents(N + 1, 0);
	vector<bool>visit(N + 1, false);

	for (y = 1; y < N; ++y) {
		cin >> num1 >> num2;
		tree[num1].push_back(num2);
		tree[num2].push_back(num1);
	}
	int num = 1;

	queue<int>q;
	q.push(1);

	while (!q.empty()) {
		visit[num] = true;
		num = q.front();
		q.pop();
		for (int cnt = 0; cnt < tree[num].size(); ++cnt) {
			if (!visit[tree[num][cnt]]) {
				parents[tree[num][cnt]] = num;
				q.push(tree[num][cnt]);
			}
		}
	}

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