취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 13237번 문제인 Binary tree이다.
문제는 아래 링크를 확인하자.

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

부모의 값으로 -1이 주어지는 노드를 루트로 삼는 트리를 만들어, 각 노드와 루트노드 사이의 거리를 구해 문제를 해결할 수 있다.

글쓴이는 BFS를 이용해 각 노드와 루트노드 사이의 거리를 구하고 문제를 해결하였다.

아래는 제출한 소스코드이다.

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

int N;
int root;
vector<int> G[21];
int ans[21];

void bfs() {
	queue<int> que;
	que.push(root);
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		for (auto& x : G[cur]) {
			ans[x] = ans[cur] + 1;
			que.push(x);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 1; i <= N; i++) {
		int x; cin >> x;
		if (x < 0) root = i;
		else G[x].emplace_back(i);
	}

	bfs();

	for (int i = 1; i <= N; i++) cout << ans[i] << '\n';
}