boj, 백준) 3108. 로고( C/C++ )

1. 문제 링크

www.acmicpc.net/problem/3108

3108번: 로고

2. 문제 개요

제일 처음에 거북이는 (0,0)에 있고 연필을 내리고 있다. 축에 평행한 직사각형 N개가 주어졌을 때, 이 직사각형을 그리는데 필요한 PU명령의 최솟값을 구하는 프로그램을 작성하시오.

 

3. 문제 힌트

각 직사각형들이 교차하거나 한 점에서 만나면 1번만 내리고도 다 그릴 수 있다.

-> 한 칸이 연결되어 있다면 다 그릴 수 있다. -> BFS

 

그럼 '각 점이 교차한다거나, 한 칸이 연결되어 있다는 것을 어떻게 표현할 수 있을까?'가 BFS로 풀이할 때의 핵심

 

4. 문제 풀이

우선 일반적인 BFS로 푼다면 다음과 같은 예외 케이스를 만날 수 있다.

예외 케이스(그림판..)

위의 그림처럼 예를들어 '선이 존재'함을 1로 값을 채울 경우, 연필을 한번 들어야 함에도 불구하고 한 번에 다 그려버리게 된다. 여기서 일반적인 BFS는 동서남북으로 1칸 모두 다 이동하는 것.

 

그래서 BFS를 위한 맵을 만들 때, 각 선이 어떻게 연결되어 있는지 구분해서 값을 채워 넣어야 한다.

 

경우의수

이 값들을 표현할때 4bit의 수로 표현했다. 0~15까지 북 남 동 서 으로 향하는 선이 존재하면 해당 비트 값을 1 올려 준다는 느낌으로 나타내었다.

 

예를 들어 좌우로 뻗어나가는 선이 이미 존재하는데 위에서 밑으로 지나가는 직사각형의 한 선분이 있다면, 그 칸은 선이 상하좌우가 되는 그런 형식이다.

그래서 코드로 옮길 때, 조금 귀찮지만 각 경우의 수에 맞게 어떤 선분이 들어오면 처리하고, 하나하나 if문을 사용해서 처리해야 하는 부분이 있어서 번거롭다.

 

물론 조금 더 생각한다면 간단하게(더 짧은 코드로) 풀 수 있는 방법을 찾을 수 있겠지만, 문제를 보자마자 팟!하고 떠오르는 알고리즘에 대해서 정당성을 따져보고 실현 가능성(문제를 풀 수 있는지?)이 있다면 그것을 코드로 옮겨보고, 정답을 확인한 뒤에 다른 사람이 어떻게 코딩을 했나 찾아보는 것도 나쁘지 않다고 생각한다.

 

disjoint set으로도 풀 수 있을 것 같던데, 찾아봐야 겠다.

 

여튼, 위처럼 맵을 나타내어 준다면,

순서대로 맵을 순회하고 BFS를 사용해서 '영역'을 찾는다.

 

하나의 영역은 붓을 한번 내려서 그릴 수 있는 모든 영역이기 때문에 이 영역을 찾는 것이 끝나면 붓을 1번 들어야만 한다.

처음 시작할 때 붓을 내리고 있기 때문에 0,0에 선분이 존재한다면 영역보다 1번 적은 횟수로 세어주도록 한다.

 

그리고 값에 음수 좌표가 있기 때문에 bias를 +500을 주도록 하자.

 

 

5. 코드

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

int n, ans;
int map[1001][1001];
bool visited[1001][1001];
//direction 'N'orth, 'S'outh, 'E'ast, 'W'est
const int N = 8, S = 4, E = 2, W = 1, EW = 3, NS = 12, NE = 10, NW = 9, SW = 5, SE = 6, NEW = 11, NSW = 13, SEW = 7, NSE = 14, NSEW = 15;
void fillrow(int x1, int x2, int y)
{
	for (int x = x1; x <= x2; ++x) {
		switch (map[y][x]) {
		case 0:
			if (x == x1)
				map[y][x] = E;
			else if (x == x2)
				map[y][x] = W;
			else
				map[y][x] = EW;
			break;
		case E:
			if (x == x1)
				map[y][x] = E;
			else if (x == x2)
				map[y][x] = EW;
			else
				map[y][x] = EW;
			break;
		case N:
			if (x == x1)
				map[y][x] = NE;
			else if (x == x2)
				map[y][x] = NW;
			else
				map[y][x] = NEW;
			break;
		case W:
			if (x == x1)
				map[y][x] = EW;
			else if (x == x2)
				map[y][x] = W;
			else
				map[y][x] = EW;
			break;
		case S:
			if (x == x1)
				map[y][x] = SE;
			else if (x == x2)
				map[y][x] = SW;
			else
				map[y][x] = SEW;
			break;
		case EW:
			if (x == x1)
				map[y][x] = EW;
			else if (x == x2)
				map[y][x] = EW;
			else
				map[y][x] = EW;
			break;
		case NS:
			if (x == x1)
				map[y][x] = NSE;
			else if (x == x2)
				map[y][x] = NSW;
			else
				map[y][x] = NSEW;
			break;
		case NE:
			if (x == x1)
				map[y][x] = NE;
			else if (x == x2)
				map[y][x] = NEW;
			else
				map[y][x] = NEW;
			break;
		case NW:
			if (x == x1)
				map[y][x] = NEW;
			else if (x == x2)
				map[y][x] = NW;
			else
				map[y][x] = NEW;
			break;
		case SW:
			if (x == x1)
				map[y][x] = SEW;
			else if (x == x2)
				map[y][x] = SW;
			else
				map[y][x] = SEW;
			break;
		case SE:
			if (x == x1)
				map[y][x] = SE;
			else if (x == x2)
				map[y][x] = SEW;
			else
				map[y][x] = SEW;
			break;
		case NEW:
			if (x == x1)
				map[y][x] = NEW;
			else if (x == x2)
				map[y][x] = NEW;
			else
				map[y][x] = NEW;
			break;
		case NSW:
			if (x == x1)
				map[y][x] = NSEW;
			else if (x == x2)
				map[y][x] = NSW;
			else
				map[y][x] = NSEW;
			break;
		case SEW:
			if (x == x1)
				map[y][x] = SEW;
			else if (x == x2)
				map[y][x] = SEW;
			else
				map[y][x] = SEW;
			break;
		case NSE:
			if (x == x1)
				map[y][x] = NSE;
			else if (x == x2)
				map[y][x] = NSEW;
			else
				map[y][x] = NSEW;
			break;
		case NSEW:
			if (x == x1)
				map[y][x] = NSEW;
			else if (x == x2)
				map[y][x] = NSEW;
			else
				map[y][x] = NSEW;
			break;
		}
	}
}
void fillcol(int y1, int y2, int x)
{
	for (int y = y1; y <= y2; ++y) {
		switch (map[y][x]) {
		case 0:
			if (y == y1)
				map[y][x] = N;
			else if (y == y2)
				map[y][x] = S;
			else
				map[y][x] = NS;
			break;
		case E:
			if (y == y1)
				map[y][x] = NE;
			else if (y == y2)
				map[y][x] = SE;
			else
				map[y][x] = NSE;
			break;
		case N:
			if (y == y1)
				map[y][x] = N;
			else if (y == y2)
				map[y][x] = NS;
			else
				map[y][x] = NS;
			break;
		case W:
			if (y == y1)
				map[y][x] = NW;
			else if (y == y2)
				map[y][x] = SW;
			else
				map[y][x] = NSW;
			break;
		case S:
			if (y == y1)
				map[y][x] = NS;
			else if (y == y2)
				map[y][x] = S;
			else
				map[y][x] = NS;
			break;
		case EW:
			if (y == y1)
				map[y][x] = NEW;
			else if (y == y2)
				map[y][x] = SEW;
			else
				map[y][x] = NSEW;
			break;
		case NS:
			if (y == y1)
				map[y][x] = N;
			else if (y == y2)
				map[y][x] = S;
			else
				map[y][x] = NS;
			break;
		case NE:
			if (y == y1)
				map[y][x] = NE;
			else if (y == y2)
				map[y][x] = NSE;
			else
				map[y][x] = NSE;
			break;
		case NW:
			if (y == y1)
				map[y][x] = NW;
			else if (y == y2)
				map[y][x] = NSW;
			else
				map[y][x] = NSW;
			break;
		case SW:
			if (y == y1)
				map[y][x] = NSW;
			else if (y == y2)
				map[y][x] = SW;
			else
				map[y][x] = NSW;
			break;
		case SE:
			if (y == y1)
				map[y][x] = NSE;
			else if (y == y2)
				map[y][x] = SE;
			else
				map[y][x] = NSE;
			break;
		case NEW:
			if (y == y1)
				map[y][x] = NEW;
			else if (y == y2)
				map[y][x] = NSEW;
			else
				map[y][x] = NSEW;
			break;
		case NSW:
			if (y == y1)
				map[y][x] = NSW;
			else if (y == y2)
				map[y][x] = NSW;
			else
				map[y][x] = NSW;
			break;
		case SEW:
			if (y == y1)
				map[y][x] = NSEW;
			else if (y == y2)
				map[y][x] = SEW;
			else
				map[y][x] = NSEW;
			break;
		case NSE:
			if (y == y1)
				map[y][x] = NSE;
			else if (y == y2)
				map[y][x] = NSE;
			else
				map[y][x] = NSE;
			break;
		case NSEW:
			if (y == y1)
				map[y][x] = NSEW;
			else if (y == y2)
				map[y][x] = NSEW;
			else
				map[y][x] = NSEW;
			break;
		}
	}
}

int main()
{
	scanf("%d", &n);
	
	for (int t = 0; t < n; ++t){
		int x1, y1, x2, y2;
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		x1 += 500; y1 += 500; x2 += 500; y2 += 500;
		fillrow(x1, x2, y1);
		fillrow(x1, x2, y2);
		fillcol(y1, y2, x1);
		fillcol(y1, y2, x2);
	}

	for (int i = 0; i <= 1000; ++i){
		for (int j = 0; j <= 1000; ++j){
			if (map[i][j] != 0 && !visited[i][j])
			{
				++ans;
				queue<pair<int, int>> q;

				visited[i][j] = true;
				q.push({ i,j });

				while (!q.empty()) {
					pair<int, int> cur = q.front(); q.pop();
					
					int dir = map[cur.first][cur.second];
					
					//W
					if (dir % 2 == 1)
					{
						pair<int, int> next;
						next.first = cur.first;
						next.second = cur.second - 1;
						if (!visited[next.first][next.second]) {
							visited[next.first][next.second] = true;
							q.push(next);
						}
					}
					dir = dir >> 1;
					//E
					if (dir % 2 == 1)
					{
						pair<int, int> next;
						next.first = cur.first;
						next.second = cur.second + 1;
						if (!visited[next.first][next.second]) {
							visited[next.first][next.second] = true;
							q.push(next);
						}
					}
					dir = dir >> 1;
					//S
					if (dir % 2 == 1)
					{
						pair<int, int> next;
						next.first = cur.first - 1;
						next.second = cur.second;
						if (!visited[next.first][next.second]) {
							visited[next.first][next.second] = true;
							q.push(next);
						}
					}
					dir = dir >> 1;
					//N
					if (dir % 2 == 1)
					{
						pair<int, int> next;
						next.first = cur.first + 1;
						next.second = cur.second;
						if (!visited[next.first][next.second]) {
							visited[next.first][next.second] = true;
							q.push(next);
						}
					}
				}
			}
		}
	}
	if (map[500][500] != 0)
		--ans;

	printf("%d", ans);
	return 0;
}

 

6. 결과