[백준][C++] 11725번: 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

 

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

 

입력으로 트리 상에서 연결된 두 정점이 주어지는데 

이를 통해 노드들을 탐색하면서 연결된 노드가 방문 처리가 안 됐으면 타고 온 노드의 자식 노드이기에 완전 탐색과 깊이탐색 두가지로 풀어보았다.

 

먼저 완전 탐색부터 보면

1. 주어진 연결 정점 쌍을 통해 그래프를 만든다.

2. 루트 노드가 1이므로 1부터 큐에 삽입

3. 삽입된 노드와 인접한 노드를 탐색하며 방문 되지 않았다면 인접한 노드를 큐에 삽입 후 삽입된 노드를 부모 노드로 저장

4. 큐가 빌 때까지 2,3번 반복

 

#include <iostream>
#include <queue>

using namespace std;

vector<int> t[100001];
int visited[100001];
int parent[100001];

void bfs() {
	queue<int> q;
	q.push(1);
	
	while(!q.empty()) {
		int x = q.front();
		visited[x] = 1;
		q.pop();
		
		for(int i=0; i<t[x].size(); i++) {
			int y = t[x][i];
			if(!visited[y]) {
				q.push(y);
				parent[y] = x;
			}
		}
	}
}

int main(void) {
	int N, a, b;
	cin >> N;
	for(int i=0; i<N-1; i++) {
		cin >> a >> b;
		t[a].push_back(b);
		t[b].push_back(a);
	}
	
	bfs();
	
	for(int i=2; i<=N; i++) {
		cout << parent[i] << "\n";
	}
}

 

 

다음으로 깊은 탐색이다.

큐 대신 재귀 함수를 사용한다는 점 말고는 기본 로직은 똑같다.

 

1. 연결 정점 쌍을 통해 그래프를 만든다.

2. 루트 노드인 1부터 탐색

3. 해당 노드의 부모 배열 값이 0이면 타고 온 노드를 부모로 저장

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> v[100001];
int parent[100001];

void dfs(int x) {
	for(int i=0; i<v[x].size(); i++) {
		int y = v[x][i];
		if(parent[y] == 0) {
			parent[y] = x;
			dfs(y);
		} 
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	
	for(int i=0; i<n-1; i++) {
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	
	parent[1] = 1;
	dfs(1);
	
	for(int i=2; i<=n; i++) {
		cout << parent[i] << "\n";
	}
}

 

 

문제와는 별개로 아래 코드가 궁금해 따로 찾아보았다. 

ios::sync_with_stdio(false);
cin.tie(0);

 

C와 C++ 표준 stream의 동기화를 비활성화하고 cin과 cout을 묶어주는 과정을 수행하지 않는 코드라고 한다.cin과 cout만 사용한다면 이를 통해 입출력 시간을 줄여주어 시간 초과를 피할 수도 있다.

 

https://dingcoding.tistory.com/62

ios::sync_with_stdio(false), cin.tie(0) 쓰는 이유, 백준 시간초과 해결