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

문제

백준 11725 문제 보기

접근 방법

bfs를 통해 부모를 찾아 저장하면 정답을 출력할 수 있다. 입력시 양방향을 다 고려해야 하는 것에 주의.

코드

#include <iostream>
#include <queue>
using namespace std;
int N;
int parents[100001];
int visited[100001];
vector<vector<int>> tree(100001);
queue<int> q;
int main() {
cin >> N;
int i, j;
// 양방향을 고려해 입력
for(int x = 0; x < N-1; x ++) {
cin >> i >> j;
tree[i].push_back(j);
tree[j].push_back(i);
}
// 루트 노드는 부모가 없으므로 처리하고 큐에 저장
parents[1] = 0;
q.push(1);
visited[1] = 1;
while(!q.empty()) {
int a = q.front();
q.pop();
// 연결된 노드에 접근한 적이 없다면 접근하고 방문처리 및 부모 설정
for(int b : tree[a]){
if(!visited[b]) {
visited[b] = 1;
parents[b] = a;
q.push(b);
}
}
}
// 출력
for(int i = 2; i <= N; i++) {
cout<< parents[i] << '\n';
}
return 0;
}
Share