[BOJ 2619 // C++] 단순 사각형

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2619번 문제인 단순 사각형이다.
문제는 아래 링크를 확인하자.

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

2619번: 단순 사각형

주어진 잘린 영역이 단순 사각형이 아닐 필요충분조건 중 하나로 주어진 N개의 점 중 하나가 내각 270도의 꼭짓점으로 포함되어있어야 할 것이 있음을 관찰하자. 내각 270도의 꼭짓점이 존재하지 않는 다각형은 단순 사각형이 될 수밖에 없고, 그러한 각도를 가질 수 있는 꼭짓점은 문제 조건에 따라 주어진 N개의 점에서 나올 수밖에 없기 때문이다.

 

글쓴이는 구현을 편하게 하기 위해 먼저 주어진 그림을 각 점과 선의 "두께"를 1로 늘려 새로 그렸다. 그 다음, 이 새 그림에 존재하는 "단순 사각형이 아닌 영역"을 메워버린 다음(위의 필요충분조건 이용) (3) 남아있는 영역의 개수를 세는 것으로 문제를 해결하자. 단순 사각형이 아닌 영역을 모두 메우면 남는 영역은 각각 단순 사각형임을 확인하자.

 

시간제한에 맞춰 통과해야하므로, 먼저 주어진 좌표들을 압축하도록 하자.

 

한편, 주어지는 입력의 꼭짓점들이 다각형을 이루는 순서대로 주어진다는 보장이 지문에 없음에 유의하자. 따라서 주어진 꼭짓점들로부터 선분들을 찾는 것부터 시작하자. 다행히 문제의 조건을 만족하는 꼭짓점들이 주어지면 이러한 선분의 구성은 유일함을 알 수 있다.

 

이 모든 과정의 시간복잡도는 $O(N^2)$으로, 이는 문제를 해결하기에 충분한 값이다.

 

아래는 제출한 소스코드이다.

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

int N;
pair<int, int> points[1000];
vector<int> R, C;
int compr_R[10001], compr_C[10001];
char board[1001][1001];

bool comp(pair<int, int>& p1, pair<int, int>& p2) {
	if (p1.second != p2.second) return p1.second < p2.second;
	return p1.first < p2.first;
}

int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

void dfs(int r, int c) {
	board[r][c] = 2;
	for (int i = 0; i < 4; i++) {
		int rr = r + dr[i], cc = c + dc[i];
		if (rr < 0 || rr > N || cc < 0 || cc > N || board[rr][cc]) continue;
		dfs(rr, cc);
	}
}

int cnt;

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

	cin >> N;

	for (int i = 0; i < N; i++) {
		int r, c; cin >> r >> c;
		points[i] = make_pair(r, c);
		R.emplace_back(r), C.emplace_back(c);
	}

	sort(R.begin(), R.end());
	for (int i = 0, ridx = 0; i < N; i++) {
		if (!compr_R[R[i]]) compr_R[R[i]] = ridx++ * 2 + 1;
	}

	sort(C.begin(), C.end());
	for (int i = 0, cidx = 0; i < N; i++) {
		if (!compr_C[C[i]]) compr_C[C[i]] = cidx++ * 2 + 1;
	}
	
	for (int i = 0; i < N; i++) {
		points[i].first = compr_R[points[i].first], points[i].second = compr_C[points[i].second];
	}
	
	sort(points, points + N);
	for (int i = 0; i < N; i += 2) {
		int r = points[i].first, c1 = points[i].second, c2 = points[i + 1].second;
		if (c1 > c2) swap(c1, c2);
		for (int c = c1; c <= c2; c++) {
			board[r][c] = 1;
		}
	}

	sort(points, points + N, comp);
	for (int i = 0; i < N; i += 2) {
		int r1 = points[i].first, r2 = points[i + 1].first, c = points[i].second;
		if (r1 > r2) swap(r1, r2);
		for (int r = r1; r <= r2; r++) {
			board[r][c] = 1;
		}
	}

	for (int i = 0; i < N; i++) {
		int r = points[i].first, c = points[i].second;
		if (board[r + 1][c] == 1 && board[r][c + 1] == 1) {
			if (!board[r - 1][c - 1]) dfs(r - 1, c - 1);
		}
		else if (board[r + 1][c] == 1 && board[r][c - 1] == 1) {
			if (!board[r - 1][c + 1]) dfs(r - 1, c + 1);
		}
		else if (board[r - 1][c] == 1 && board[r][c + 1] == 1) {
			if (!board[r + 1][c - 1]) dfs(r + 1, c - 1);
		}
		else if (board[r - 1][c] == 1 && board[r][c - 1] == 1) {
			if (!board[r + 1][c + 1]) dfs(r + 1, c + 1);
		}
	}

	for (int r = 0; r <= N; r++) {
		for (int c = 0; c <= N; c++) {
			if (!board[r][c]) dfs(r, c), cnt++;
		}
	}

	cout << cnt;
}