취미로 코딩하기

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

이번에 볼 문제는 백준 3108번 문제인 로고이다.
문제는 아래 링크를 확인하자.

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

각 점의 x좌표와 y좌표의 값이 -500 이상 500 이하이므로 입력으로 주어질 수 있는 좌표의 가짓수는 1,002,001이다. 각 좌표값에 500을 더해 음이 아닌 정수로 취급해 문제를 해결해도 답은 달라지지 않음을 이용해 편히 구현하자. (단, 원점의 좌표 또한 같이 바뀌는 점에 유의하자.)

각 (직사각형을 그리는 데에 사용된) 좌표를 노드로, 직사각형의 변으로 (인접하게) 연결된 두 노드 사이의 관계를 에지로 나타내면 주어진 화면의 도형을 최대 노드 1,002,001개의 그래프로 모델링할 수 있다. 이 그래프의 connected component의 개수를 세어 문제를 해결하자. 노드가 $V$개인 그래프의 connected component의 개수는 다양한 탐색을 이용해 $O(V)$에 구할 수 있으므로 시간복잡도는 충분하다.

원래의 도형이 (0,0)을 지난다면 처음에 PU 연산을 한번 덜 사용해도 되는 점을 잊지 않고 구현하자.

아래의 구현은 각 좌표를 2배로 잡은 뒤 두 인접한 노드의 연결여부를 사이 인덱스의 값을 이용해 표현한 것으로, 위의 설명과 대동소이하다.

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

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

int N;
int arr[2001][2001];
int cnt;

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

void bfs(int qR, int qC) {
	queue<pair<int, int>> que;
	que.push(make_pair(qR, qC));
	arr[qR][qC] = 0;
	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr < 0 || rr>2000 || cc < 0 || cc>2000 || arr[rr][cc] == 0) continue;
			arr[rr][cc] = 0;
			que.push(make_pair(rr, cc));
		}
	}
}

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

	cin >> N;
	while (N--) {
		int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2;
		if (r1 > r2) swap(r1, r2);
		if (c1 > c2) swap(c1, c2);
		r1 = r1 * 2 + 1000, r2 = r2 * 2 + 1000, c1 = c1 * 2 + 1000, c2 = c2 * 2 + 1000;
		
		for (int r = r1; r <= r2; r++) arr[r][c1] = arr[r][c2] = 1;
		for (int c = c1; c <= c2; c++) arr[r1][c] = arr[r2][c] = 1;
	}

	if (arr[1000][1000]) cnt--;

	for (int r = 0; r < 2001; r++) {
		for (int c = 0; c < 2001; c++) {
			if (arr[r][c]) {
				cnt++;
				bfs(r, c);
			}
		}
	}

	cout << cnt;
}