[백준] 11725 - 트리의 부모 찾기 (C++)

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

루트가 없는 트리가 주어지고 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 2 ≤ N ≤ 100,000

 

트리를 탐색하기 위해 너비 우선 탐색(BFS)이나 깊이 우선 탐색(DFS)을 사용할 수 있다. BFS면 queue를 사용하고, DFS면 stack을 사용하거나 재귀 함수로 만들어 진행한다.

 

너비 우선 탐색(Breath First Search)

• queue 자료구조 사용
• 한 노드에서 다른 특정 노드로 가는 최단 경로를 찾을 수 있음

BFS

 

깊이 우선 탐색(Depth First Search)

• stack 자료구조 사용 or 재귀 함수로 진행
• 한 노드에서 다른 특정 노드로 가는 path나 cycle을 찾을 수 있음

DFS

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N, 간선 정보 입력받기
   1. 간선 정보 양방향으로 저장
2. 트리의 루트인 1번 노드부터 bfs 함수로 트리 탐색 시작하기
   1. queue를 이용해 부모와 연결된 자식을 방문하기 전 부모 정보를 저장하고 queue에 넣으면서 진행
3. 2번부터 N번까지 각 노드의 부모 노드 번호 출력하기

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

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

int n,x,y,parent[100001];
bool visit[100001];
vector<int> edge[100001];

void bfs(int start) {
    queue<int> q;
    q.push(start);
    visit[start] = true;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (auto i : edge[cur]) {
            if (!visit[i]) {
                q.push(i);
                visit[i] = true;
                parent[i] = cur;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(); cout.tie();

    cin >> n;
    for (int i=1; i<n; i++) {
        cin >> x >> y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    bfs(1);
    for (int i=2; i<=n; i++)
        cout << parent[i] << '\n';
}