[백준] 3108-로고(C++)

문제링크: https://www.acmicpc.net/problem/3108

3108번: 로고

 

전형적인 한붓그리기 문제라고 하는데 어려움을 겪었습니다.

마이너스 좌표는 +500을 더해줌으로 해결했는데,

아래와 같은 그림에서 멘붕이 왔습니다.

 

위 처럼 네모가 둘이 붙어있으면 일반  탐색으로는 붙어 있는 걸로 처리 되었기 때문입니다.

 

이를 해결하기 위해서  동서남북 4방향을 저장하는 배열을 작성하면서 제작하려 해보았지만, 

실패...

 

얍문님 티스토리를 통해서 좌표값에 2배를 곱해줌으로서 쉽게 이러한 문제를 해결할 수 있단 걸 

알게되었습니다. (감사함다.)

 

 

 

 

접근방식

 

1. 좌표값을 (a + 500) * 2로 만든후 직사각형들을 색칠

 

2. 일반 bfs를 통해서 연결된 도형들을 탐색하면서 갯수를 세어주자

 

 

문제풀이 

 

1. 좌표값에 (a + 500) * 2 를 해주기

 

2. (0,0) 좌표인 arr[1000][1000]을 미리 bfs로 탐색해주기.

( 제일 처음에 거북이는 (0,0)에 있고, 거북이가 보고 있는 방향은 y축이 증가하는 방향이다. 또한 연필은 내리고 있다. )

 

3. 0,0부터 2000,2000까지 bfs로 탐색하면서 뭉쳐진 도형들을 색칠해주며 갯수 세기

 

아래는 정답 코드

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

int n, result ;
int x1, y11, x2, y2;

bool arr[2001][2001] = { 0, };
bool visited[2001][2001] = { 0, };

int y_ar[4] = { -1,0,1,0 };
int x_ar[4] = { 0,1,0,-1 };


void bfs(int y, int x) {
	queue <pair<int, int>> que;
	que.push(make_pair(y, x));
	visited[y][x] = 1;

	while (!que.empty()) {
		int cy = que.front().first;
		int cx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];
			if (ny < 0 || ny > 2000 || nx < 0 || nx > 2000)
				continue;
			if (visited[ny][nx] != 0 || arr[ny][nx] != 1)
				continue;
			visited[ny][nx] = 1;
			que.push(make_pair(ny, nx));

		}



	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {

		cin >> x1 >> y11 >> x2 >> y2;
		x1 = (x1 + 500) * 2;
		y11 = (y11 + 500) * 2;
		x2 = (x2 + 500) * 2;
		y2 = (y2 + 500) * 2;

		for (int i = x1; i <= x2; i++) {
			arr[y11][i] = 1;
			arr[y2][i] = 1;
		}
		for (int i = y11; i <= y2; i++) {
			arr[i][x1] = 1;
			arr[i][x2] = 1;
		}
	}

	
	if(arr[1000][1000] == 1)
		bfs(1000, 1000);

	for (int i = 0; i <= 2000; i++)
		for (int j = 0; j <= 2000; j++)
			if (arr[i][j] == 1 && visited[i][j] == 0) {
				bfs(i, j);
				result++;
			}

	cout << result << endl;

	return 0;
}