[P4] 백준 13306번 트리 C++ 유니온 파인드, 오프라인 쿼리

리뷰

 

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

오프라인쿼리를 통해 쿼리를 모두 받은 후 유니온 파인드를 통해 처리해 주는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 노드의 개수를 저장할 변수
• q : 쿼리의 개수를 저장할 변수
• par : 부모 노드의 번호를 저장할 배열
• nodes : 자신이 속한 그룹의 루트 노드 번호를 저장할 배열
• Query : 쿼리 정보를 정의할 구조체

 

함수

1. Find

int Find(int a) {
	if (nodes[a] == a) return a;
	return nodes[a] = Find(nodes[a]);
}

 

자신이 속한 루트 노드의 번호를 찾기 위한 함수, 경로 압축까지 진행해 준다.

 

2. Union

void Union(int a, int b) {
	int A = Find(a);
	int B = Find(b);
	if (A == B) return;
	nodes[B] = A;
}

 

두 노드의 루트 노드 번호를 찾고, 유니온 처리를 해주기 위한 함수

 

 

문제풀이

1. n, q값을 입력 받고, nodes[1]의 값을 1로 저장해 준다.
2. 2~n번 노드를 순회하며 par배열에 자신의 부모 노드 번호를 저장하고, nodes에 자기 자신을 값으로 저장한다.
3. Query타입 벡터 queries를 초기화 하고, q+n-1개의 쿼리를 입력 받아 쿼리 정보를 저장해 준다.
4. string타입 벡터 res를 초기화 하고, queries가 빌때까지 while루프를 수행, 매 루프마다 쿼리를 한개씩 꺼내어 준다.
5. query.op가 1일경우 Find함수를 통해 query.v1, query.v2의 루트 노드번호가 같다면 "YES\n"를 아니라면 "NO\n"를 res에 추가해 준다.
6. query.op가 0일경우 par[query.v1]과 query.v1을 Union함수에 전달하여 같은 그룹에 속하게 해준다.
7. 모든 쿼리를 처리한 후 res배열을 뒤에서 부터 순회하며 정답을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 초기 루트 노드 번호는 자신으로 설정하고 op가 0인 쿼리가 나올때마다 Union처리해 주면 된다.
2. op가 1인 쿼리의 경우 Find함수를 통해 루트 노드의 번호가 같은지를 비교해 주면 된다.

 

정답 코드

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

const int N = 2e5 + 1;
int n, q;
int par[N];
int nodes[N];
struct Query {
	int op, v1, v2;
};

int Find(int a) {
	if (nodes[a] == a) return a;
	return nodes[a] = Find(nodes[a]);
}

void Union(int a, int b) {
	int A = Find(a);
	int B = Find(b);
	if (A == B) return;
	nodes[B] = A;
}

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

	nodes[1] = 1;
	for (int i = 2; i <= n; ++i) {
		cin >> par[i];
		nodes[i] = i;
	}

	vector<Query> queries;
	for (int i = 0; i < q + n - 1; ++i) {
		int op;  cin >> op;

		if (op) {
			int v1, v2; cin >> v1 >> v2;
			queries.push_back({ op, v1, v2 });
		}
		else {
			int v1; cin >> v1;
			queries.push_back({ op, v1 });
		}
	}

	vector<string> res;
	while (!queries.empty()) {
		Query query = queries.back(); queries.pop_back();
		
		if (query.op) {
			if (Find(query.v1) == Find(query.v2)) res.push_back("YES\n");
			else res.push_back("NO\n");
		}
		else Union(par[query.v1], query.v1);
	}

	for (int i = res.size() - 1; i >= 0; --i) cout << res[i];
}