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

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

그래프, 트리 관련 문제이다.

 

우선 (n+1)*(n+1) 행렬을 만들어서 트리를 인접 행렬을 통해 나타내는 방식을 생각해볼 수 있다.

노드가 양방향으로 연결되어있기 때문에 (1,6)을 받으면 (1,6)과 (6,1) 모두 저장한다.

 

하지만 이런 방식으로 풀면 비어있는 공간도 모두 탐색하면서 시간이 오래 걸려 시간 초과가 날 것 같아서 다른 방법을 생각해보았다.

2차원 벡터를 사용하여 노드와 연결된 노드만 저장하는 방식이다.

vector[1] : 4, 6

vector[2] : 4

....

이런식으로 만들었다.

 

우선 루트가 1이라고 했으니 큐에 1을 넣고 시작한 뒤 노드 r을 1로 저장하고 pop을 한번 해준다. 그리고 vector[r] 을 탐색하면서 원소가 아직 방문이 되지 않았을 경우에 해당 원소를 큐에 넣고 방문했다고 표시한다. 그리고 정답을 저장하는 배열에 해당 원소의 부모 노드는 r이라고 저장한다. 이런 식으로 모든 노드를 탐색하는 bfs방식을 사용해 문제를 풀었다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>

using namespace std;
typedef long long ll;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, nod1, nod2;
	cin >> n;
	vector<vector<int>> tree(n + 1, vector<int>());
	vector<bool> visited(n + 1, false);
	vector<int> ans(n + 1);
	queue<int> rq;

	for (int i = 0; i < n - 1; i++) {
		cin >> nod1 >> nod2;
		tree[nod1].push_back(nod2);
		tree[nod2].push_back(nod1);
	}

	rq.push(1);
	while (!rq.empty()) {
		int row = rq.front();
		rq.pop();
		for (int i = 0; i < tree[row].size(); i++) {
			if (!visited[tree[row][i]]) {
				ans[tree[row][i]] = row;
				visited[tree[row][i]] = true;
				rq.push(tree[row][i]);
			}
		}
	}
	for (int i = 2; i <= n; i++) {
		cout << ans[i] << "\n";
	}
};