[백준 3108] 로고

분류 : dfs/bfs

 

요구사항

N개의 직사각형을 그리는 필요한 PU명령의 최솟값을 출력한다.

-> dfs 진입하는 횟수 구하기

 

풀이

처음에 좌표를 +500,+500으로 잡으니 이어져있지 않더라도 옆에 있으면 이어지는 현상이 나타났다

해결 방법은 +500해주고 다시 *2를 해줌으로 직사각형 사이즈를 2배 증가 시켯다

 

이후는 단순히 2000*2000 배열을 dfs 탐색하면 된다

 

#include <iostream>

using namespace std;
int n;
int map[2200][2200];
int ans = 0;
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,-1,0,1 };
void dfs(int r, int c) {

	//cout << r << " " << c << endl;
	for (int i = 0; i < 4; i++) {
		int nr = r + dr[i];
		int nc = c + dc[i];
		if (nr < 0 || nc < 0 || nr > 2000 || nc > 2000) continue;
		if (map[nr][nc] == 1) {
			map[nr][nc] = 2;
		//	cout << "!" << endl;
			dfs(nr, nc);
		}

	}
}
void solve() {
	for (int i = 0; i <= 2000; i++) {
		for (int j = 0; j <= 2000; j++) {
			if (map[i][j] == 1) {
				ans++;
				dfs(i, j);
			}
		}
	}
//	cout << ans << endl;
	if (map[1000][1000] == 2)
	{
	//	cout << "!" << endl;
		ans--;
	}
}
int main() {
	scanf("%d", &n);

	//입력 받아주고 사각형 위치에 1 적어주기
	for (int i = 0; i < n; i++) {
		int x1, x2, y1, y2;
		scanf("%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 = y1; j <= y2; j++) {
			map[x1][j] = 1;
			map[x2][j] = 1;
		}
		for (int j = x1; j <= x2; j++) {
			map[j][y1] = 1;
			map[j][y2] = 1;
		}
	}
	solve();
	printf("%d\n", ans);

}