문제

풀이

나는 세그먼트 트리를 이용해 풀었다.
세그먼트 트리의 a~b구간에 있는 모든 노드가 false 라면 false를 리턴하도록 구성하였다.

일반적인 세그먼트 트리의 Sum 연산은 left 와 right 안에 start, end 범위가 포함되면 바로 return을 해주지만 이 문제에선 start ~ end 사이의 모든 노드가 false인 경우만 return 해주고 그렇지 않다면 다시 start ~ mid , mid+1 ~ end 의 구간에 대해 재귀적으로 호출하며 각 구간을 false로 바꾸어주는 작업을 했다.

wall 배열에는 벽에 대한 정보를 저장했다.
(wall[x] : x번방과 x+1번방 사이의 벽 존재 유무)

모든 연산 후 wall 배열의 상태를 통해 방의 개수를 세주었다.

void breakWall(vector<bool>& tree, bool wall[], int node, int start, int end, int left, int right) {
	if (left > end || right < start) return;
	if (left <= start && end <= right) {
		if (tree[node] == false) return; 
        //left~right에 start~end 범위가 포함되며 모두 false
        
        else tree[node] = false;
		//그렇지 않다면 tree[node]를 false로 바꾸어 주고 start~mid , mid+1~end 구간에 대해 같은 작업을 반복
	}

	if (start == end) {
		wall[start] = false;
		return;
	}
	int mid = (start + end) / 2;
	breakWall(tree, wall, node * 2, start, mid, left, right);
	breakWall(tree, wall, node * 2 + 1, mid + 1, end, left, right);
}

전체코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <string>
using namespace std;

int n, m;
void input() {
	cin >> n >> m;
}
bool init(vector<bool>& tree, int node, int start, int end) {
	if (start == end) return tree[node] = true;
	int mid = (start + end) / 2;
	return tree[node] = init(tree, node * 2, start, mid) && init(tree, node * 2 + 1, mid + 1, end);
}

void breakWall(vector<bool>& tree, bool wall[], int node, int start, int end, int left, int right) {
	if (left > end || right < start) return;
	if (left <= start && end <= right) {
		if (tree[node] == false) return;
		else tree[node] = false;

	}

	if (start == end) {
		wall[start] = false;
		return;
	}
	int mid = (start + end) / 2;
	breakWall(tree, wall, node * 2, start, mid, left, right);
	breakWall(tree, wall, node * 2 + 1, mid + 1, end, left, right);
}


void solve() {
	input();

	int h = (int)ceil(log2(n));
	int tree_size = (1 << (h + 1));
	vector<bool> tree(tree_size+1, true);
	bool wall[1000001];
	fill(wall, wall + 1000001, true);

	init(tree, 1, 1, n - 1);
		for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		breakWall(tree, wall, 1, 1, n, a, b - 1);
	}

	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (wall[i]) {
			if (wall[i - 1]) {
				ans++;
			}
		}
		else {
			while (!wall[i]) i++;
			i--;
				
			ans++;

		}
	}
	cout << ans;
}




int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	solve();
}

후기

풀고나니 Union-Find로 해결 가능한 문제였다.
이 풀이의 핵심은 방을 합쳐나가는 과정에서 합쳐진 방들의 parents를 가장 오른쪽 방으로 고정시켜 skip 하는 것이다.
위 풀이로는 다음에 다시 풀어봐야 겠다.