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

문제

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

---

풀이

[DFS/BFS]

node 1부터 시작하여 연결된 노드를 탐색하며 부모 노드를 확인한다.

 

+) BFS가 더 효율적인 것을 볼 수 있다.

---

코드

1️⃣ DFS

#include <iostream>
#include <unordered_map>
#include <vector>
#include <stack>
using namespace std;
int visited[100001] = { 0 };
int result[100001] = { 0 };
vector<vector<int>> tree;

void check(int node, int parent) {
	result[node] = parent;

	for (int i = 0; i < tree[node].size(); i++) {
		int next = tree[node][i];
		if (visited[next] != 0)continue;
		visited[next] = 1;
		check(next,node);
	}
}

int main() {

	//INPUT
	int N; cin >> N;
	tree = vector<vector<int>>(N+1);
	int n1, n2;
	for (int i = 0; i < N-1; i++) {
		cin >> n1 >> n2;
		tree[n1].push_back(n2);
		tree[n2].push_back(n1);
	}

	//CACULATE
	visited[1] = 1;
	check(1, 0);

	//RESULT
	for (int i = 2; i <= N; i++) {
		cout << result[i] << "\n";
	}

}

2️⃣ BFS

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

vector<vector<int>> tree;
int result[100001] = {0};


int main() {

	//INPUT
    int N; cin >> N;
    tree.resize(N + 1);
    int n1, n2;
    for (int i = 0; i < N - 1; i++) {
        cin >> n1 >> n2;
        tree[n1].push_back(n2);
        tree[n2].push_back(n1);
    }
	
    
    //CALCULATE
    queue<int> q;
    q.push(1);

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

        for (int next : tree[node]) {
            if (result[next] == 0) {
                result[next] = node;
                q.push(next);
            }
        }
    }


	//RESULT
    for (int i = 2; i <= N; i++) {
        cout << result[i] << "\n";
    }
}