[C++]백준 - 11725번 문제

11725번: 트리의 부모 찾기 (acmicpc.net)

11725번: 트리의 부모 찾기

 

11725번 : 트리의 부모 찾기

---

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

 

입력

---

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

 

 

출력

---

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

 

 

---

 

생각해 볼 점

---

* 트리는 순환이 없는 그래프입니다.

 

* 순환이 없으므로 루트에서 탐색을 시작하면, 다음 노드는 반드시 이전 노드의 자식입니다.

 

이 두 가지만 숙지하면, 문제를 푸는 데에 문제가 없습니다.

 

코드

---

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

int main() 
{
    int N;
    scanf("%d", &N);
    
    //동적 할당
    vector<int> *graph = new vector<int>[N + 1];
    bool *visited = new bool[N + 1];
    int *parent = new int[N + 1];
    fill_n(visited, N + 1, false);
    fill_n(parent, N + 1, 0);
    parent[1] =  -1;
    
    //입력부
    for(int i = 1; i < N; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    //BFS알고리즘
    queue<int> q;
    q.push(1);
    visited[1] = true;
    while(!q.empty())
    {
        int current = q.front();
        q.pop();
        //루트에서 아래로 내려가므로, 다음 간선은 current의 자식임
        for(int next : graph[current])
        {
            if(!visited[next])
            {
                parent[next] = current;
                q.push(next);
                visited[next] = true;
            }
        }
    }
    
    
    for(int i = 2; i < N + 1; i++) printf("%d\n", parent[i]);
    
    delete[] graph;
    delete[] visited;
    delete[] parent;
	return 0;
}

 

그 외

---