[백준 11725] 트리의 부모 찾기

C++에는 트리에 대한 STL이 따로 없다.
그래서 있는 걸로 만들어야함
근데 이걸 자료구조 수업때 한 것처럼 죄다 Node 구조체 껴서 만드는건 미친짓임 ㅇㅇ...
 
인접행렬은 시간복잡도랑 공간복잡도가 개쓰레기 수준이니

 

그냥 vector 배열이나 unordered_map으로 인접리스트형식을 구현해주면 됨 
난 vector 배열 구현을 더 선호. 시간이 더 적게 걸림

 

---

 

트리 부모 찾는데 다른 단순한 방법이 있을까 생각해봤는데 없다.
 
우선 DFS로 품.
DFS 하면서 해당 자식 찾으면 해당 자식의 노드list로 들어가기 전에
stack에 현재 위치만 push해주면 됨.

1. DFS

#include <iostream>
#include <vector>
#include <stack>
#define SIZE 100001

using namespace std;

int arr[SIZE];
bool visited[SIZE];

vector<int> tree[SIZE];

void DFS(int vertex) {
	stack<int> s;
	s.push(1);
	visited[1] = true;

	while (!s.empty()) {
		vertex = s.top();
		s.pop();

		auto it = tree[vertex].begin();

		while (it != tree[vertex].end()) {
			if (!visited[*it]) {
				visited[*it] = true;
				arr[*it] = vertex;

				s.push(vertex);
				vertex = *it;
				it = tree[vertex].begin();
			}
			else { it++; }
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N, A, B; cin >> N;

	for (int i = 0; i < N - 1; i++) {
		cin >> A >> B;
		tree[A].push_back(B);
		tree[B].push_back(A);
	}

	DFS(1);
	for (int i = 2; i <= N; i++) cout << arr[i] << "\n";
	return 0;
}

while (it != tree[vertex].end()) {
	if (!visited[*it]) {
		visited[*it] = true;
		arr[*it] = vertex;

		s.push(vertex);
		vertex = *it;
		it = tree[vertex].begin();
	}
}

 
근데 DFS는 백트래킹을 해서 이미 visited한 노드들도 또 확인을 함. 그래서 비효율적
그래서 BFS로도 도전

 

---

2. BFS

#include <iostream>
#include <list>
#include <queue>
#define SIZE 100001

using namespace std;

int arr[SIZE];
bool visited[SIZE];
vector<int> tree[SIZE];

void BFS(int vertex) {
	queue<int> q;
	q.push(vertex);
	visited[vertex] = true;

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

		for (const auto& next : tree[cur]) {
			if (!visited[next]) {
				visited[next] = true;
				arr[next] = cur;
				q.push(next);
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int N, A, B; cin >> N;

	for (int i = 0; i < N-1; i++) {
		cin >> A >> B;
		tree[A].push_back(B);
		tree[B].push_back(A);
	}
	BFS(1);
    
	for (int i = 2; i <= N; i++) cout << arr[i] << "\n";
	return 0;
}