[BAEKJOON] 11725번. 트리의 부모 찾기.cpp

#. Problem

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

* The copyright in this matter is in BAEKJOON

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

    - tree

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. 각 노드들의 연결 상태를 vector에 list형태로 저장

  2. 각 노드마다 방문 상태를 chk array에 저장하면서 방문(1번 root 노드부터 시작)

     -> queue에 1번(root)노드부터 방문을 하면서, 각 노드와 연결된 노드들을 queue에 넣어줌.

     -> queue가 비어있을 때까지 반복

  3. 

#. Code

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

#include <iostream> #include <vector> #include <queue>   using namespace std;   // Maximum number of nodes #define MAX 100001       int N; int parent[MAX];    // save parent nodes bool chk[MAX];        // check visited nodes vector<int> arr[MAX];    // tree list   int main() {     // Improving iostream performance     ios::sync_with_stdio(false);       cin >> N;       for (int i = 0; i < N - 1; i++)     {         int n1, n2;           cin >> n1 >> n2;           arr[n1].push_back(n2); arr[n2].push_back(n1);     }       queue<int> q;       parent[1] = 0; // Root has no parent     chk[1] = true;     q.push(1);       // BFS process     while (!q.empty())     {         int x = q.front(); q.pop();         for (int y : arr[x]) // range-based for         {             if (!chk[y])             {                 chk[y] = true;                 parent[y] = x;                 q.push(y);             }         }     }       for (int i = 2; i <= N; i++)         cout << parent[i] << "\n";       return 0; } Colored by Color Scripter

cs

11) 각 노드들의 부모 노드를 저장

12) 노드 방문 상태를 저장

13) 노드의 연결 상태를 저장

22~29) vector에 list 형식으로 노드의 연결 상태를 저장한다.

31) queue는 i번째 노드와 연결된 노드들을 정보를 저장하기 위해 사용. 

33~35) 트리의 root를 1로 가정하고 초기화

38~50) 노드들의 정보가 저장된 queue가 비어있을 때까지 반복,

         40) queue에 저장된 노드를 하나씩 빼면서 부모 노드를 확인,

         41~49) 해당 노드와 연결된 노드들을 방문,

                   해당 노드(자식 노드)가 방문되지 않았을 시, 방문 상태와 해당 노드의 parent를 저장하고,

                   queue에 해당 노드(자식 노드)를 저장

#. Result

  - Input --------------------------------------------------------

7

1 6

6 3

3 5

4 1

2 4

4 7

------------------------------------------------------------------

  - Output --------------------------------------------------------

4

6

1

3

1

4

------------------------------------------------------------------