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

11725번: 트리의 부모 찾기

 

 

트리의 성질을 이용한 BFS 문제입니다.

 

먼저, 트리의 부모 노드에서 자식 노드 방향으로 검사합니다.

루트 노드는 1이므로, 1부터 BFS를 이용해 검사하게 되면, 모든 노드들의 부모를 알 수 있게 됩니다.

 

그림을 그리면 더 쉽게 이해할 수 있습니다.

 

 

<예제 입력 1>

 

 

 

루트 노드인 1부터 BFS 탐색을 하면서 이전에 방문을 한 적이 있으면 isChecked[index] = true로 바꿔줍니다.

이렇게 탐색을 진행하게 될 경우, 어떤 노드에서 다음으로 방문할 노드들은 자식 노드임이 성립하게 되는 것을 알 수 있습니다.

 

 

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

int N;
vector<vector<int> > v;
int parent[100001];
bool isChecked[100001];

void input() {
  cin >> N;
  v.resize(N + 1);
  for (int i = 0; i < N - 1; i++) {
    int x, y;
    cin >> x >> y;
    v[x].push_back(y);
    v[y].push_back(x);
  }
}

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

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

    for (int nx : v[x]) {
      if (!isChecked[nx]) {
        parent[nx] = x;
        isChecked[nx] = true;
        q.push(nx);
      }
    }
  }
}

void printAnswer() {
  for (int i = 2; i <= N; i++) {
    cout << parent[i] << '\n';
  }
}

int main() {
  ios::sync_with_stdio(false);

  input();
  bfs();
  printAnswer();
  
  return 0;
}