트리의 부모 찾기 (feat. 백준, 11725번)

트리의 부모 찾기
https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <map>
#include <set>
using namespace std;
map<int, set<int>> tree;
int ans[100001];
bool visit[100001];
void bfs() {
	queue<int> q;
	q.push(1);
	visit[1] = true;
	while (!q.empty()) {
		auto v = q.front(); q.pop();
		for (auto iter = tree[v].begin(); iter != tree[v].end(); ++iter)
			if (!visit[*iter])
				visit[*iter] = true, ans[*iter] = v, q.push(*iter);
	}
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N;
	cin >> N;
	memset(visit, false, N + 1);
	memset(ans, 0, sizeof(ans[0] * (N + 1)));
	for (register int n = 1, x, y; n < N; ++n)
		cin >> x >> y, tree[x].insert(y), tree[y].insert(x);
	bfs();
	for (register int i = 2; i <= N; ++i)
		cout << ans[i] << "\n";
	return 0;
}
// *&)*@*

BFS 풀이 방법

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <map>
#include <set>
using namespace std;
map<int, set<int>> tree;
int ans[100001];
bool visit[100001];
void dfs(register int n) {
	for (auto iter = tree[n].begin(); iter != tree[n].end(); ++iter)
		if (!visit[*iter])
			visit[*iter] = true, ans[*iter] = n, dfs(*iter);
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N;
	cin >> N;
	memset(visit, false, N + 1);
	memset(ans, 0, sizeof(ans[0] * (N + 1)));
	for (register int n = 1, x, y; n < N; ++n)
		cin >> x >> y, tree[x].insert(y), tree[y].insert(x);
	dfs(1);
	for (register int i = 2; i <= N; ++i)
		cout << ans[i] << "\n";
	return 0;
}
// *&)*@*

DFS 풀이 방법

 

bfs, dfs 모두 풀이가 가능한 문제입니다.

해당 문제를 첫번째 예제를 통해 보면 다음과 같습니다.

1 - 6 / 6 - 3 / 3 - 5 / 4 - 1 / 2 - 4 / 4 - 7 끼리 연결되어 있습니다. 또한 문제에서 트리의 루트는 1이라고 하였으므로 1부터 시작합니다.

문제로 입력받은 tree와 해당 값을 통해 답을 도출하는 ans 배열은 아래와 같이 표현할 수 있습니다.

부모 1은 자식 6, 4를 갖고, 부모 2는 자식 4를 갖고 ... 부모 7은 자식 4를 갖습니다.

루트 1을 시작으로, 부모 1은 자식 6과 4를 갖고 있습니다. 따라서 자식 6과 4는 1을 채워주고 다음 체크는 6 -> 4를 진행합니다.

부모 6은 자식 1과 3을 갖습니다. 따라서 자식 1과 3은 6을 채워주고 다음 체크는 4 -> 1 -> 3을 진행합니다.

부모 4는 자식 1, 2, 7을 갖고 있습니다. 자식 1은 이미 채워졌으므로 건너띄고 2와 7은 4를 채워주고 다음 체크는 1 -> 3 -> 2 -> 7을 진행합니다.

부모 1은 이미 이전에 진행되었으므로 건너띕니다.

부모 3은 자식 6, 5를 갖습니다. 자식 6은 이미 채워졌으므로 건너띄고 5는 3을 채워줍니다. ans이 모두 진행되었으므로 종료합니다.

따라서 문제는 2번 노드부터 출력하도록 하였으므로 ans[2] ~ ans[7]까지를 출력합니다.