11725번 트리의 부모 찾기 | BFS, DFS | Baekjoon BOJ 백준 11725 C++ 코드, 해설, 풀이

 

 

 

이번 포스팅은 백준 11725번 트리의 부모 찾기입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

 

 

 

기본 알고리즘

BFS 너비 우선 탐색

DFS 깊이 우선 탐색

 

 

답안 출력 시 (line 48)

 

 

cout << parent[i] << endl;  //시간 초과

 

printf("%d\n", parent[i]);  //해결

 

 

 

전체 코드

 

BFS 너비 우선 탐색

 

//백준11725 트리의부모찾기                                         
 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int n;
const int MAX = 100001;
vector<int> map[MAX];
bool visited[MAX];
int parent[MAX];
queue<int> q;
 
void BFS(int v) {
    visited[v] = true;
    q.push(v);
 
    while (!q.empty()) {
        v = q.front();
        q.pop();
 
        for (vector<int>::iterator iter = map[v].begin(); iter != map[v].end(); ++iter){
            int w = *iter;
            if (visited[w] == 0) {
                parent[w] = v;
                visited[w] = true;
                q.push(w);
            }
        }
    }
 
}
 
int main() {
    cin >> n;
 
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        map[x].push_back(y);
        map[y].push_back(x);
    }
 
    BFS(1);
 
    for (int i = 2; i <= n; i++) {
        printf("%d\n", parent[i]);
    }
}

 

 

 

DFS 깊이 우선 탐색

 

//백준11725 트리의부모찾기                                         
 
#include <iostream>
#include <vector>
using namespace std;
 
int n;
const int MAX = 100001;
vector<int> map[MAX];
bool visited[MAX];
int parent[MAX];
 
void DFS(int v) {
    visited[v] = true;
 
    for (vector<int>::iterator iter = map[v].begin(); iter != map[v].end(); ++iter) {
        int w = *iter;
        if (visited[w] == 0) {
            parent[w] = v;
            DFS(w);
        }
    }
}
 
int main() {
    cin >> n;
 
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        map[x].push_back(y);
        map[y].push_back(x);
    }
 
    DFS(1);
 
    for (int i = 2; i <= n; i++) {
        printf("%d\n", parent[i]);
    }
}