[C++][BOJ 11725] 트리의 부모 찾기

 

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

11725번: 트리의 부모 찾기

 

BFS로 풀 수도 있고, DFS로도 풀 수 있는 문제다. 아직 방문하지 않은 정점인 경우 현재 방문 노드를 아직 방문하지 않은 노드의 부모로 check하고 방문 여부를 true로 바꿔주면 되는 문제다.

 

주의 사항으로는 c++에서 endl을 사용하는 경우에는 cout과정에서 시간을 오래 잡아먹어 시간초과가 나오므로 \n을 사용해야 한다.

 

코드는 아래에 있다.

 

dfs 코드

#include <bits/stdc++.h>
using namespace std;

vector<int> graph[100001];

bool check[100001];
int parent[100001];

void dfs(int cur){
	check[cur]=true;
	
	for(int i=0;i<graph[cur].size();i++){
		int nxt=graph[cur][i];
		if(!check[nxt]){
			parent[nxt]=cur;
			dfs(nxt);
		}
	}
}

int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n;
	cin >> n;
	
	for(int i=1;i<n;i++){
		int from,to;
		cin >> from >> to;
		
		graph[from].push_back(to);
		graph[to].push_back(from);
	}
	
	for(int i=1;i<=n;i++){
		sort(graph[i].begin(),graph[i].end());
	}
	
	dfs(1);
	
	for(int i=2;i<=n;i++){
		cout << parent[i] << '\n';
	}
	
	return 0;
}

 

bfs 코드

#include <bits/stdc++.h>
using namespace std;

vector<int> graph[100001];

bool check[100001];
int parent[100001];

void bfs(){
	queue<int> q;
	q.push(1);
	
	check[1]=true;
		
	while(!q.empty()){
		int cur=q.front();
		q.pop();
		
		for(int i=0;i<graph[cur].size();i++){
			int nxt=graph[cur][i];
			if(!check[nxt]){
				parent[nxt]=cur;
				q.push(nxt);
				check[nxt]=true;
			}
		}
	}
}

int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n;
	cin >> n;
	
	for(int i=1;i<n;i++){
		int from,to;
		cin >> from >> to;
		
		graph[from].push_back(to);
		graph[to].push_back(from);
	}
	
	for(int i=1;i<=n;i++){
		sort(graph[i].begin(),graph[i].end());
	}
	
	bfs();
	
	for(int i=2;i<=n;i++){
		cout << parent[i] << '\n';
	}
	
	return 0;
}

 

코드 길이는 dfs가 더 짧지만 bfs 방식이 메모리와 시간에서는 더 효율적이다.