3108번: 로고

문제 설명

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

3108번: 로고

[문제]

 로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다.

 거북이는 위치와 각도로 표현할 수 있다. 거북이는 입에 연필을 물고 있는데, 연필을 내리면 움직일 때 화면에 선을 그리고, 올리면 선을 그리지 않고 그냥 지나가기만 한다.

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

 사용자는 다음과 같은 다섯가지 명령으로 거북이를 조정할 수 있다.

1. FD x: 거북이를 x만큼 앞으로 전진
2. LT a: 거북이를 반시계 방향으로 a도 만큼 회전
3. RT a: 거북이를 시계 방향으로 a도 만큼 회전
4. PU: 연필을 올린다
5. PD: 연필을 내린다.

 축에 평행한 직사각형 N개가 주어졌을 때, 이 직사각형을 그리는데 필요한 PU 명령의 최솟값을 구하는 프로그램을 작성하시오.

 거북이는 같은 선을 여러 번 그릴 수 있지만, 문제에 주어진 직사각형 N개를 제외한 어떤 것도 그릴 수 없다. 거북이의 크기는 아주 작아서 좌표 평면의 한 점이라고 생각하면 된다. 직사각형의 변은 축에 평행하다.

 

[입력]

 첫째 줄에 직사각형의 개수 N이 주어진다. (1 ≤ N ≤ 1000)

 다음 N개의 줄에는 직사각형의 좌표 x1, y1, x2, y2가 주어진다. (−500 ≤ x1 < x2 ≤ 500), (−500 ≤ y1 < y2 ≤ 500) (x1, y1)는 직사각형의 한 꼭짓점 좌표이고, (x2, y2)는 그 점의 대각선 방향의 반대 꼭짓점의 좌표이다.

 

[출력]

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

 

[예제 입력 1]

1
0 0 10 10

[예제 출력 1]

0

[예제 입력 2]

1
-5 -5 5 5

[예제 출력 2]

1

[예제 입력 3]

5
1 1 4 4
3 3 6 6
4 4 5 5
5 0 8 3
6 1 7 2

[예제 출력 3]

2

---

풀이

 흔히 그룹을 찾을 때 사용하는 union-find 방식을 찾아내는 게 매우 핵심인 문제였다. 

 초기에는 2차원 배열에 좌표를 보정한 직사각형을 그린 다음 BFS 탐색을 통해 연결된 곳을 모두 동일한 인덱스로 표시하려 했지만, 이러한 방식에서는 직사각형 2개가 겹친 상태는 아니지만 붙어있을 경우 BFS를 통해 동일한 그룹으로 묶여 질 문제가 있다.

1	1	1	1	1	1
1		2	2	2	1
1		2		2	1
1		2	2	2	1
1	1	1	1	1	1

  결국 겹치는 것을 표현하려면 현재 직사각형을 표시하는 과정에서 겹치는 좌표에 해당하는 직사각형을 바로 같은 그룹으로 묶어야 하는데, 이를 일종의 트리 형태로 묶는 것으로 코드를 작성했다.

 우선 각 직사각형의 부모를 저장하는 배열을 만들고 -1로 초기화한다. 이후 각 직사각형을 그리는 과정에서 겹치는 직사각형들의 최상단 부모(루트 노드)를 찾아, 이들의 부모를 현재 직사각형으로 초기화하는 것이다. 이렇게 되면 현재 직사각형을 그리는 과정에서 만나는 직사각형의 그룹들을 모두 현재 직사각형 그룹에 속하게 묶을 수 있다.

 이렇게 주어진 직사각형을 모두 그린 다음, 부모 배열을 처음부터 조사하여 값이 -1인 것의 개수만 세면, 이들의 개수가 바로 현 직사각형들이 묶여진 그룹의 개수가 된다. 이 때 문제에서 원하는 출력은 (0, 0)이 속한 그룹은 바로 그릴 수 있기 때문에, 그룹의 개수 - 1을 하여 이를 출력하면 된다.

#include <iostream>
#include <cstring>

using namespace std;

int parent[1001];
int canvas[1001][1001];

int findRoot(int num) {//최상단 부모 반환
	while (parent[num] != -1)
		num = parent[num];

	return num;
}

int main() {
	int N, x1, y1, x2, y2;
	int answer = -1;

	memset(parent, -1, sizeof(parent));
	memset(canvas, -1, sizeof(canvas));

	cin >> N;

	canvas[500][500] = 0;

	for (int i = 1; i <= N; i++) {//각 사각형에 대해
		cin >> x1 >> y1 >> x2 >> y2;

		for (int r = y1; r <= y2; r++)
			for (int c = x1; c <= x2; c++) {
				if (r == y1 || r == y2 || c == x1 || c == x2) {
					if (canvas[r + 500][c + 500] != -1) {//그리는 곳에 다른 사각형이 존재
						int root = findRoot(canvas[r + 500][c + 500]);//해당 사각형의 최상단 부모를 반환
						if (root != i)//현재 자기 자신이 아니라면
							parent[root] = i;//해당 최상단 부모의 부모를 추가
					}
					canvas[r + 500][c + 500] = i;//이후 자신의 값으로 표시
				}
			}
	}

	for (int i = 0; i <= N; i++)//부모가 -1(자신이 최상단인 것만 카운트)
		if (parent[i] == -1)
			++answer;

	cout << answer;

	return 0;
}

---

결과