백준 11725. 트리의 부모 찾기 (트리 bfs, dfs)

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

11725번: 트리의 부모 찾기

 

1. 재귀 dfs

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

int n;
int u, w;
vector<int> adj[100002];
int p[100002];

void dfs(int cur)
{
    for(auto nxt : adj[cur])
    {
        if(p[cur] == nxt) continue; // 부모 노드로 가는 것을 막음.
        p[nxt] = cur;
        dfs(nxt);
    }
}
int main()
{           
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 0; i < n - 1; i++)
    {
        cin >> u >> w; 
        adj[u].push_back(w);
        adj[w].push_back(u);
    }

    dfs(1);  
    for(int i =2; i <= n; i++) cout << p[i] << '\n';  
}

2. 비재귀 dfs

#include <iostream>
#include <unordered_set>
#include <vector>
#include <stack>
using namespace std;

int n;
int u, w;
vector<int> adj[100002];
int p[100002];

void dfs(int sv)
{
    stack<int> _stack;
    _stack.push(sv);

    while(!_stack.empty())
    {
        int cur = _stack.top();
        _stack.pop();

        for(auto m: adj[cur])
        {
            if(p[cur] == m) continue;
            p[m] = cur;
            _stack.push(m);
        }
    }

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

    cin >> n;
    for(int i = 0; i < n - 1; i++)
    {
        cin >> u >> w; 
        adj[u].push_back(w);
        adj[w].push_back(u);
    }

    dfs(1);  
    for(int i =2; i <= n; i++) cout << p[i] << '\n';  
}

3. bfs

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

int n;
int u, w;
vector<int> adj[100002];
int p[100002];

void bfs(int sv)
{
    queue<int> _queue;
    _queue.push(sv);

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

        for(auto m: adj[cur])
        {
            if(p[cur] == m) continue;
            p[m] = cur;
            _queue.push(m);
        }
    }

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

    cin >> n;
    for(int i = 0; i < n - 1; i++)
    {
        cin >> u >> w; 
        adj[u].push_back(w);
        adj[w].push_back(u);
    }

    bfs(1);  
    for(int i =2; i <= n; i++) cout << p[i] << '\n';  
}