백준 11725번 [트리의 부모 찾기](C++)-yes6686- 티스토리

백준 문제 풀이: 11725 [트리의 부모 찾기]

---

문제 링크: https://www.acmicpc.net/problem/11725

문제 설명:

루트가 1인 트리가 주어질 때, 각 노드의 부모를 구하는 문제입니다. 트리는 무방향 그래프로 주어지며, n개의 노드와 n-1개의 간선을 가집니다.

입력:

• 첫째 줄에 노드의 개수 n (2 ≤ n ≤ 100,000)이 주어집니다.
• 다음 n-1개의 줄에 간선 정보가 주어집니다. 각 줄에는 두 정수 x, y가 주어지며, 이는 노드 x와 노드 y가 연결되어 있음을 나타냅니다.

출력:

• 2번 노드부터 n번 노드까지의 부모를 한 줄에 하나씩 출력합니다.

---

문제 해결 코드

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

vector tree[100001];
int parent[100001];
bool visited[100001];

void findParents(int root) {
    queue q;
    q.push(root);
    visited[root] = true;

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

        for (int child : tree[current]) {
            if (!visited[child]) {
                visited[child] = true;
                parent[child] = current;
                q.push(child);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }

    findParents(1);

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

    return 0;
}

예제

입력:
7
1 6
6 3
3 5
4 1
2 4
4 7

출력:
4
6
1
3
1
4

---

코드 설명

• 그래프 생성:
  • 트리를 인접 리스트로 표현합니다.
• 루트에서 BFS 실행:
  • 1번 노드를 루트로 설정하고 BFS를 수행하여 각 노드의 부모를 구합니다.
  • 방문한 노드는 visited 배열로 체크합니다.
• 부모 노드 출력:
  • 2번 노드부터 n번 노드까지 부모를 출력합니다.

시간 복잡도

• 트리는 n개의 노드와 n-1개의 간선을 가지므로 BFS의 시간 복잡도는 O(n)입니다.

---

결과

코드는 입력된 트리 구조를 정확히 탐색하며, 각 노드의 부모를 효율적으로 계산합니다. BFS를 사용해 O(n)의 시간 복잡도로 문제를 해결하며, 대규모 입력에도 적합합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!