백준 11725 트리의 부모 찾기 풀이

문제

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

&Title
11725번 - 트리의 부모 찾기

&Question
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 
정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 

&Input
첫째 줄에 노드의 개수 N (2 ≤ N 
≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 
연결된 두 정점이 주어진다. 

&Output
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 
번호를 2번 노드부터 순서대로 출력한다. 

&Example
-input
7
1 6
6 3
3 5
4 1
2 4
4 7

-output
4
6
1
3
1
4

-input
12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

-output
1
1
2
3
3
4
4
5
5
6
6

요약

• 트리에 대한 정보가 주어질때, 각 노드의 부모노드를 출력하라

접근

• 각 트리를 양방향으로 연결해준다(어느 노드가 먼저 선택될지 모르므로)
• dfs로 노드1부터 시작해서 탐색한다.

풀이

1. 양방향으로 연결
2. 노드1를 시작으로 방문함. 역방향으로 가는것 방지, 방문체크만 해주면된다.

    void dfs(int value) {
        visited[value] = true;
   
        for (int& v : tree[value]) {
            if (visited[v])continue;
            parent[v] = value;
            dfs(v);
        }
    }
   

틀렸던 이유

• 정직하게 트리 구현해서 짰더니 시간초과 났다.. insert할때 마다 넣을 곳을 찾는데 O(n)이라;;
• 이래서 배열로 구현하나보다 ㅡㅠ

소스

먼저 시간 초과났던 소스이다. 답 자체는 잘나온다(아마도 -ㅅ-)

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

struct node {
	int value;
	vector<node*> next;

	node(int key) : value(key) {}
};

node* root = new node(1);
int parent[100001];

void insert(int a, int b, node* leaf) {
	if (leaf == NULL)return;
	if (a == leaf->value) {
		leaf->next.push_back(new node(b));
		parent[b] = a;
	}
	else if (b == leaf->value) {
		leaf->next.push_back(new node(a));
		parent[a] = b;
	}
	else {
		for (node* k : leaf->next) {
			insert(a, b, k);
		}
	}
}

int n;

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	int a, b;
	for (int i = 2; i <= n; ++i) {
		cin >> a >> b;
		insert(a, b, root);
	}

	for (int i = 2; i <= n; ++i) {
		cout << parent[i] << '\n';
	}
	return 0;
}

dfs를 이용해 루트노드부터 이어진 노드를 탐색하는 방식으로 푼 풀이이다.

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

int n;
bool visited[100001];
int parent[100001];
vector<int> tree[100001];

void dfs(int value) {
	visited[value] = true;

	for (int& v : tree[value]) {
		if (visited[v])continue;
		parent[v] = value;
		dfs(v);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;

	int a, b;
	for (int i = 2; i <= n; ++i) {
		cin >> a >> b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}

	dfs(1);

	for (int i = 2; i <= n; ++i)
		cout << parent[i] << '\n';
	return 0;
}