백준 13306 - 트리(C++)

문제 링크입니다. https://www.acmicpc.net/problem/13306

13306번: 트리

오프라인 쿼리 문제였습니다.

간선을 지운다는 것을 거꾸로 생각하는 것이 핵심이였습니다.

들어오는 입력을 먼저 확인하겠습니다.

2번째 줄부터 N-1개 만큼 트리를 확인할 수 있는 정보가 입력됩니다.

예제 입력 1번의 경우는 1번이 2번의 부모, 1번이 3번의 부모라는 의미입니다.

 

트리 정보가 주어진 후에는 제거할 선과 연결되어 있는 지를 확인할 노드들의 정보가 주어집니다.

제거할 선의 경우, X가 0이며 B와 B의 부모를 제거하겠다는 의미입니다.

연결되어 있는 지를 확인하는 노드의 경우 X가 1이며, C와 D가 연결되어 있는 지를 확인하겠다는 의미입니다.

 

트리를 실제로 구현한 후, 직접 선을 제거해 나가면서 연결되어 있는지 확인하는 것은 어렵습니다.

이때 생각해 봐야할 것이 끊는 것과 잇는 것은 서로 반대 개념이라는 것입니다.

문제에서는 N-1개의 선을 항상 제거합니다. 이는 모든 트리의 간선을 제거하겠다는 의미입니다.

따라서 제거할 선을 반대로 시작하여 연결해 나가면 원래의 트리를 구할 수 있습니다.

해당 방법은 최소 스패닝 트리를 사용하면 쉽게 구현할 수 있습니다.

 

입력을 거꾸로 확인하는 것이 핵심이라는 것을 알았으니 노드가 연결되어 있는지를 확인해야합니다.

문제에서 주어진 예제 입력2의 트리를 직접 그린 뒤, 반대로 행하면 답이 같게 나온다는 것을 쉽게 알 수 있습니다.

이는 역순으로 시작했기에 연결됐는지의 여부도 거꾸로 확인하면 결국에는 답과 같다는 것을 알 수 있습니다.

 

노드를 확인하는 방법은 최소 스패닝 트리에서 Find 함수를 이용하면 할 수 있습니다. 하지만 일반적인 Find와 Union을 통해서는 트리 내에서 같은 부모를 가지고 있더라도 같은 곳을 향하게 만드는 것이 불가능 할 수 있습니다.

따라서 Rank라는 배열을 이용해 X번 노드가 트리에서 어디에 위치해 있는지를 저장해준뒤, Rank 값에 따라서 선을 연결합니다. 노드의 가장 높은 부모에 연결시킬 수 있습니다. 

해당 과정을 거친 뒤, Find 함수를 사용한다면 부모가 같은지 확인하는 것만으로 서로 연결되었는지 확인이 가능합니다.

 

과정을 거꾸로 했기에 정답도 거꾸로 저장이 되있습니다. 따라서 stack을 이용해 빼주면 정상적으로 답이 나올 수 있습니다.

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <cstring>
#include <string>
#define INF 987654321
#define P pair<int,int>
#define PP pair<int, P>
using namespace std;

int N, Q;
int Node_Parent[200001]; // X번째 노드의 부모를 저장 
int Node_connect[200001];
int Node_rank[200001];

stack<PP> st;
stack<string> ans;

void reset_connect() {
	for (int i = 1; i <= N; i++) {
		Node_connect[i] = i;
		Node_rank[i] = 1;
	}
}

int Find(int x) {
	if (Node_connect[x] == x) return x;
	else return Node_connect[x] = Find(Node_connect[x]);
}

void Union(int x, int y) {
	int X = Find(x);
	int Y = Find(y);
	if (X != Y) {
		// 노드의 rank를 확인한다. 더 높은 곳이 부모임으로 높은 곳에 연결한다.
		if (Node_rank[X] > Node_rank[Y]) {
			Node_connect[Y] = X;
		}
		else {
			Node_connect[X] = Y;
			//Y 밑에 X를 연결했음으로 서로의 rank가 같다면 Y를 더 크게 해준다.
			if (Node_rank[X] == Node_rank[Y]) Node_rank[Y]++;
		}
	}
}

void solve() {
	reset_connect();
	while (!st.empty()) {
		int x = st.top().first;
		if (x == 0) {
			int node = st.top().second.first;
			int parent = st.top().second.second;
			Union(node, parent);
		}
		else {
			int F_x = st.top().second.first;
			int F_y = st.top().second.second;
			//부모에 항상 연결되도록 했기에 부모가 같다면 만날 수 있다
			if (Find(F_x) == Find(F_y)) ans.push("YES");
			else ans.push("NO");
		}
		st.pop();
	}
	while (!ans.empty()) {
		cout << ans.top() << "\n";
		ans.pop();
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> Q;
	for (int i = 1; i < N; i++) {
		int parent_node;
		cin >> parent_node;
		Node_Parent[i + 1] = parent_node;
	}
	Node_Parent[1] = 1;
	int Quest = N - 1 + Q;
	for (int i = 1; i <= Quest; i++) {
		int x, b, c, d;
		cin >> x;
		if (x == 0) {
			cin >> b;
			st.push({ 0, {b,Node_Parent[b]} });
		}
		else {
			cin >> c >> d;
			st.push({ x,{c,d} });
		}
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요