[BOJ/Gold 2] 백준 14595 동방 프로젝트 (Large)(C++)

문제 링크

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

14595번: 동방 프로젝트 (Large)

 

문제

동아리방이 가지고 싶었던 병찬이는 LINK 사업단에 문의하여 N개의 방 중의 하나를 얻을 기회를 얻었다. 일자로 되어있는 건물에 N개의 방은 일직선상에 존재하며, 각 방에는 번호가 매겨져 있다. 맨 왼쪽 방의 번호는 1번이며, 순서대로 증가하여 맨 오른쪽 방의 번호가 N번이다. 각 방 사이에는 방을 구분하는 벽이 존재한다.

물론 병찬이 외에도 많은 사람이 동아리방을 원한다. 다행히 방은 충분했기에 병찬이는 안심하고 있었지만…

그때였다.

빅-종빈빌런이 나타나 건물 벽을 허물기 시작한 것이다! 빅-종빈빌런은 다음과 같은 규칙으로 벽을 무너뜨린다.

• x < y 를 만족하는 두 방에 대해서 x번 방부터 y번 방 사이에 있는 모든 벽을 허문다.
• 두 방 사이의 벽이 허물어지면 두 방은 하나의 방으로 합쳐진다.
• 이미 허물어진 벽이 존재한다면 무시하고 다음 벽을 허문다.
• 빅-종빈빌런은 건물이 무너지는 걸 원치 않기 때문에, 1번 방의 왼쪽 벽과 N번 방의 오른쪽 벽(즉, 바깥과 연결된 벽)은 허물지 않는다.

동아리 방의 개수가 점점 줄어들자 병찬이는 초조해졌다. 이에 병찬이는 동아리방을 얻을 수 있는지에 대한 확률을 계산하기 위해 남는 동아리방의 수를 구하고 싶어 한다. 병찬이를 위해 빅-종빈빌런의 행동 횟수 M과 동방의 개수 N이 주어졌을 때, 남은 동아리방의 수를 구해주자.

입력

첫 번째 줄에는 동아리방의 개수를 나타내는 양의 정수 N(2 ≤ N ≤ 1,000,000) 이 주어진다. 두 번째 줄에는 빅-종빈빌런의 행동 횟수를 나타내는 음이 아닌 정수 M(0 ≤ M ≤ 5,000) 이 주어진다. 세 번째 줄부터 M개의 줄에 걸쳐 빅-종빈빌런의 행동이 양의 정수 x, y(1 ≤ x < y ≤ N) 로 주어진다. 여기서 행동이란 x번 방부터 y번 방 사이의 벽을 무너뜨리는 것을 의미한다.

빅-종빈빌런은 매우 허당이기 때문에 동일한 행동을 여러 번 할 수 있음에 유의하라.

출력

빅-종빈빌런의 모든 행동이 끝난 후 남아있는 동방의 개수를 한 줄에 출력한다.

예제 입력 1

5
2
1 2
2 4

예제 출력 1

2

예제 입력 2

5
1
1 5

예제 출력 2

1

예제 입력 3

10
3
1 3
2 4
5 8

예제 출력 3

4

예제 입력 4

100
0

예제 출력 4

100

힌트

첫 번째 행동으로 1번과 2번 방이 합쳐져 (1, 2), (3), (4), (5) 상태가 된다. 이후 두 번째 행동으로 2, 3, 4번 방이 합쳐져 (1, 2, 3, 4), (5)의 상태가 된다. 따라서 남아있는 동방의 수는 2가 된다.

알고리즘 분류

• 유니온 파인드

풀이

벽을 부순다는 것은 방과 방 사이를 합친다는 뜻이므로, 유니온 파인드를 활용한다.

유니온 파인드를 활용하되, 마지막으로 부순 벽 오른쪽의 방을 기억하고(Last_Break) 다음 명령을 수행할 때 Last_Break 앞쪽에 있는 방 사이의 벽들은 부술 필요가 없으므로 Last_Break번 방 쪽에 위치한 벽부터 부순다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 1000001
#define LL long long
#define INF 1e9

using namespace std;
int N, M;
int Parent[MAX];
bool visited[MAX];
int Last_Break = 0;
vector<pair<int, int> > Vec;
int answer = 0;

void Init() {
	for (int i = 1; i <= N; i++) {
		Parent[i] = i;
	}
}

int Find(int X) {
	if (Parent[X] == X) {
		return X;
	}
	return Parent[X] = Find(Parent[X]);
}

void Union(int X, int Y) {
	int PX = Find(X);
	int PY = Find(Y);
	if (PX != PY) {
		Parent[PY] = PX;
	}
}

void Input() {
	cin >> N >> M;
	Init();
	for (int i = 0; i < M; i++) {
		int X, Y;
		cin >> X >> Y;
		Vec.push_back(make_pair(X, Y));
	}
}

void Settings() {
	sort(Vec.begin(), Vec.end());
	for (int i = 0; i < Vec.size(); i++) {
		int S = Vec[i].first;
		int E = Vec[i].second;
		S = max(S, Last_Break);
		for (int i = S; i <= E; i++) {
			Union(S, i);
		}
		Last_Break = max(Last_Break, E);
	}
}

void Find_Answer() {
	for (int i = 1; i <= N; i++) {
		int P = Find(i);
		if (!visited[P]) {
			visited[P] = true;
			answer++;
		}
	}
	cout << answer << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}