[11725번] 트리의 부모 찾기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Tree에 대한 이해

2. BFS

큐를 통해 각 레벨 당 트리의 부모를 찾을 수 있다.

기존의 BFS와 다른 점을 하나 소개 하자면, 

기존 BFS는 check 배열을 통해 방문을 했는지 확인 하고 또다른 배열을 통해 값을 넣는 방식을 이용한다.

하지만 이 코드에서는 check배열을 따로 두지 않고, parent 배열을 check배열과 값을 넣는 배열 역할을 동시에 하도록 하는 방식이다.

그러한 차이점을 고려하며 BFS에 대한 새로운 관점도 보면 좋을 것 같다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

#include <iostream> #include <cstdio> #include <vector> #include <queue>   using namespace std;   vector<int> tree[100002]; int parent[100002];   queue<int> q;   // bfs를 통해 트리의 부모 노드를 찾아낸다. void bfs(int here) {     q.push(here);       while (!q.empty())     {         int next = q.front();         q.pop();           for (int i = 0; i < tree[next].size(); i++)         {             // 부모 노드가 존재하지 않는다면             if (!parent[tree[next].at(i)])             {                 q.push(tree[next].at(i));                 parent[tree[next].at(i)] = next;             }         }     } } int main() {     int n;     int from, to;       scanf("%d", &n);       // 트리 생성     for (int i = 0; i < n - 1; i++)     {         scanf("%d %d", &from, &to);         tree[from].push_back(to);         tree[to].push_back(from);     }         bfs(1);          for (int i = 2; i <= n; i++)         printf("%d\n", parent[i]);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus