취미로 코딩하기

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

이번에 볼 문제는 백준 2620번 문제인 직각다각형의 면적 구하기이다.
문제는 아래 링크를 확인하자.

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

먼저, 구현을 편하게 하기 위해 주어진 도형을 각 점과 선의 "두께"를 1로 늘려 새로 그리자. 시간 제한과 메모리 제한을 생각하지 않는다면, 새로 그린 도형의 (도형의 바깥을 제외한) 각 영역에 대하여 행 또는 열이 다른 직선의 연장선에 포함되지 않은 칸들의 개수의 최댓값을 구하는 것으로 문제를 해결할 수 있을 것이다.

시간 제한과 메모리 제한을 통과하기 위해 각 점들의 좌표를 1000 이하의 정수로 줄이고, 각 칸의 너비와 높이가 줄어들기 전에 얼마였는지를 기록하는 방식을 이용하자. 이 때 각 영역의 칸의 개수를 세는 과정은 각 칸의 너비와 높이를 곱한 값의 합을 구하는 것으로 바뀐다. 다른 직선의 연장선에 해당하는 칸의 경우 그 직선의 방향에 따른 높이 또는 너비를 0으로 계산하면 별다른 예외처리 없이 이를 구현해낼 수 있음을 확인하자.

위와 같이 구현할 경우 시간복잡도는 $O(N^2)$이 되고, 이는 문제를 해결하기에 충분한 시간복잡도이다.

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

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

int N;
int R[1000], C[1000];
int dR[1000], dC[1000];
int compr_R[10001], compr_C[10001];
pair<int, int> points[1000];

int board[1001][1001];
int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };
int dfs(int r, int c) {
	board[r][c] = 1;
	int ret = dR[r] * dC[c];
	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;
		ret += dfs(rr, cc);
	}

	return ret;
}

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 ans;

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

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

	sort(R, R + N);
	for (int i = 0, idxR = 0; i < N; i++) {
		if (!compr_R[R[i]]) {
			if (i) dR[idxR * 2] = R[i] - R[i - 1];
			compr_R[R[i]] = idxR++ * 2 + 1;
		}
	}

	sort(C, C + N);
	for (int i = 0, idxC = 0; i < N; i++) {
		if (!compr_C[C[i]]) {
			if (i) dC[idxC * 2] = C[i] - C[i - 1];
			compr_C[C[i]] = idxC++ * 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;
		}
	}

	dfs(0, 0);

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

	cout << ans;
}