[백준][C++] 14595: 동방 프로젝트 (Large)

문제 링크: https://www.acmicpc.net/problem/14595

 

문제 이름이 동방 프로젝트네요. 10덕 그게 아니고 동아리방입니다😅

동방 프로젝트 (Small) 문제는 그냥 아무렇게나 풀면 되는데 Large 문제는 N, M이 크기 때문에 고민을 좀 해봐야 합니다.

 

여러 방법으로 풀 수 있는 문제인데 유니온 파인드로 풀어봤습니다.

동방을 각각 집합으로 만들고, 벽을 부수면 union 하는 식으로 하면 되겠죠? 그런데 이미 부순 벽을 또 부수게 하면 시간낭비가 있기 때문에 적당히 skip을 해줘야 합니다.

저는 합쳐진 동방의 root가 합쳐진 방중에 맨 오른쪽 방이 되게 하는 식으로 구현했습니다.

 

[x, y]를 합친다고 했을 때,

• x의 루트의 오른쪽 칸을 저장 (next = find(x)+1)
• x와 y를 합치고 (merge(x,y)
• x를 저장했던 값으로 교체 (x=next)
• x와 y의 루트의 값이 같지 않을 때까지 이 과정을 반복

 

\[N - \text{벽을 부순 횟수} = \text{남은 동방의 수}\]

남은 동방의 수를 세려면 위 식처럼 계산하면 되겠죠?

 

#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;


vector<int> parent;

void init(int n) {
	parent.resize(n);
	for (int i = 0; i < n; ++i)
		parent[i] = i;
}

int find(int u) {
	if (u == parent[u]) return u;
	return parent[u] = find(parent[u]);
}

void merge(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return;

	parent[u] = v;
}


int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n, m;
	cin >> n >> m;
	int x, y;
	init(n);

	int dongbang = n;
	while (m--) {
		cin >> x >> y;
		--x, --y;

		while (find(x) != find(y)) {
			--dongbang;

			int next = find(x) + 1;
			merge(x, y);
			x = next;
		}
	}

	cout << dongbang << '\n';


	return 0;
}

union by rank를 쓰면 틀렸습니다가 나오는데 왜일까요

 

지금 알고리즘에서는 x부터 오른쪽으로 한칸씩 합쳐나가는 방식인데 그 경우 무조건 루트가 맨 오른쪽이 되겠죠. 그래서 next=find(x)+1이 됩니다

하지만 union by rank로 만들면 루트가 맨 오른쪽이 아닐 수도 있기 때문에 틀릴 수 있습니다.

 

근데 반례를 좀 만들려고 해봤는데 잘 안떠오르네요;; 아몰랑