백준-3108 로고

---

문제

---

실수한 부분

처음에 문제가 이해가 안되어 생각하는데 조금 시간이 흘렀다. (0,0)에 PU(연필 올리기)에 신경을 쓰다보니, 마지막 답을 도출할 때, -1을 해준다는 걸 생각못해서 그걸 잡는다고 또 많은 고민을 했다.

구현

한붓 그리기 문제였다.
겹치는 사각형을 탐색할 때, 사각형끼리 통화하지 않고 거리가 1차이로 다른 사각형을 한붓 그리기로 인식하는 걸 방지하기 위해 좌표에 2를 곱해주었다.
그리고 좌표값의 범위가 -500부터 이므로 500을 더해 배열에 담을 수 있도록 해주었다.

#include <bits/stdc++.h>

using namespace std;

struct Turtle {
	int x;
	int y;
};

int Board[2001][2001] = { 0, };
int N;
int delTurtle[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };

bool isValid(int x, int y) {
	if (0 > x || x > 2000 || 0 > y || y > 2000)
		return false;
	if (Board[y][x] == 0 || Board[y][x] == 2)
		return false;
	return true;
}

void bfs(int x, int y) {
	queue<Turtle> Q;
	Q.push({ x,y });

	while (!Q.empty()) {
		int curX = Q.front().x;
		int curY = Q.front().y;
		Q.pop();

		for (int i = 0; i < 4; ++i) {
			int nX = curX + delTurtle[i][0];
			int nY = curY + delTurtle[i][1];

			if (!isValid(nX, nY))
				continue;

			Board[nY][nX] = 2;
			Q.push({ nX,nY });
		}
	}
}

int main() {
	scanf_s("%d", &N);

	for (int i = 0; i < N; ++i) {
		int x1, y1, x2, y2;
		scanf_s("%d %d %d %d", &x1, &y1, &x2, &y2);

		x1 = (x1 + 500) * 2; x2 = (x2 + 500) * 2;
		y1 = (y1 + 500) * 2; y2 = (y2 + 500) * 2;

		for (int j = x1; j <= x2; ++j) {
			Board[y1][j] = 1;
			Board[y2][j] = 1;
		}
		for (int j = y1; j <= y2; ++j) {
			Board[j][x1] = 1;
			Board[j][x2] = 1;
		}
	}

	int answer = Board[1000][1000] == 1 ? 0 : 1;

	for (int i = 0; i < 2001; ++i) {
		for (int j = 0; j < 2001; ++j) {
			if (Board[i][j] == 1) {
				answer++;
				Board[i][j] = 2;
				bfs(j, i);
			}
		}
	}
	printf("%d", answer == 0 ? 0 : answer - 1);
}