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

문제

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

풀이과정

각 노드의 연결 상태를 입력으로 받고 각 노드의 부모노드 번호를 출력하는 문제이다.
트리의 입력을 그래프처럼 인접리스트로 받은 후에 BFS로 탐색하며 parent 배열에 부모노드 번호를 저장하면 된다.

처음 예제입력을 BFS로 탐색해보면 처음 1 다음에는 큐에 4와 6이 들어가며 parent[4]와 parent[6]의 값은 부모노드 번호인 1이 들어가게 된다. 다음 과정을 살펴보면 큐의 front값이 4이므로 parent[2]와 parent[7]의 값은 부모노드 번호인 4로 된다. 이렇게 BFS를 통하여 부모노드를 저장하는 방법으로 해결할 수 있는 문제였다.

소스코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define MAX 100001

int N;
int parent[MAX];
bool chk[MAX];
vector<int> a[MAX];

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

    cin >> N;

    for (int i = 0; i < N-1; i++)
    {
        int u, v;

        cin >> u >> v;

        a[u].push_back(v); a[v].push_back(u);
    }

    queue<int> q;

    parent[1] = 0; // 루트의 부모는 없다 
    chk[1] = true;
    q.push(1);

    // BFS 과정
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        for (int y : a[x]) // 범위 기반 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;
}