11725번 - 트리의 부모 찾기

📌문제

👉 문제보기

코드

#include <iostream>
#include <vector>
#include <queue>
#define MAX_SIZE 100001
using namespace std;

int n; // 노드의 개수
bool visited[MAX_SIZE];
int arr[MAX_SIZE];

void bfs(vector<vector<int>> vec) {
    queue<int> q;

    q.push(1);

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

        for (int i = 0; i < vec[cur].size(); i++) {
            int next = vec[cur][i];
            if (!visited[next]) {
                visited[next] = true;
                q.push(next);
                arr[next] = cur;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;

    vector<vector<int>> vec(n + 1);

    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        
        vec[x].push_back(y);
        vec[y].push_back(x);
    }
    
    bfs(vec);

    for (int i = 2; i <= n; i++) {
        cout << arr[i] << '\n';
    }

    return 0;
}

🍳문제 풀이

이 문제는 부모와 연결되지 않은 다른 트리와 이어졌을 때 부모를 잘 찾아야 하는 것이 핵심 같았다!
입력 받은 값들을 양방향 연결을 해주고, BFS 에서 다음 노드를 방문하지 않은 경우, visited 체크해주고, Q에 넣어준다. arr 배열은 부모 노드의 값을 저장한다.
마지막에 2번째 노드부터 arr배열에 담긴 값을 출력해주면 각자 노드의 바로 윗 부모를 출력할 수 있다.

테스트 해봤던 입력 값
8
2 3
4 6
5 7
5 8
3 5
5 4
1 2