문제
로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다.
거북이는 위치와 각도로 표현할 수 있다. 거북이는 입에 연필을 물고 있는데, 연필을 내리면 움직일 때 화면에 선을 그리고, 올리면 선을 그리지 않고 그냥 지나가기만 한다.
제일 처음에 거북이는 (0,0)에 있고, 거북이가 보고 있는 방향은 y축이 증가하는 방향이다. 또한 연필은 내리고 있다.
사용자는 다음과 같은 다섯가지 명령으로 거북이를 조정할 수 있다.
FD x: 거북이를 x만큼 앞으로 전진
LT a: 거북이를 반시계 방향으로 a도 만큼 회전
RT a: 거북이를 시계 방향으로 a도 만큼 회전
PU: 연필을 올린다
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)는 그 점의 대각선 방향의 반대 꼭짓점의 좌표이다.
5
1 1 4 4
3 3 6 6
4 4 5 5
5 0 8 3
6 1 7 2
출력
N개의 직사각형을 그리는 필요한 PU명령의 최솟값을 출력한다.
2
문제 접근
이 문제는 굉장히 난해해서 다른 분의 풀이를 참고했습니다.(https://yabmoons.tistory.com/179)
문제를 이해하기가 조금 어려웠다. 그렇지만 꼭 알아야할 점을 정리하자면
1. 음수 좌표는 표현하기 애매하다 -500~500 까지의 좌표를 평행이동 처리한다.
2. 사각형의 사이를 1/0으로 구분할 수 있지만 겹치지 않게 하려면 곱하기 2를해주면 거리를 둘 수 있고 그렇게 되면 DFS 탐색시 새로운 사각형으로 인지 할 수 있다.
참고한 블로그의 예시를 가져오면
(3,3)~ (6,6) 사각형과
(4,4) ~ (5,5) 사각형이 겹쳐지게 표현된다는 것이다. 예를들어
board[2001][2001] 보드에서 사각형을 표현하고 싶으면
for (x = x1; x <= x2; ++x) {
board[y1][x] = 1;
board[y2][x] = 1;
}
for (y = y1; y <= y2; ++y) {
board[y][x1] = 1;
board[y][x2] = 1;
}이렇게 표현할건데, 이렇게 되면
이렇게 값들이 1로 표시될텐데, 사실상
이렇게 표현되면 한붓그리기(DFS) 탐색시에 하나의 사각형으로 인식하게 된다. 그렇다면 어떻게 모눈종이처럼 띄울 수 있을까?
-> 좌표에 *2를 해서 해결할 수 있다.
좌표에 곱하기 2를 해주면 양끝 대각선만 주기 때문에
(6,6) ~ (12,12)
(8,8) ~ (10,10) 이렇게 되면 곱한 2만큼의 간격이 생기게 된것이다.
이렇게 되면 DFS 방문시 서로 다른 사각형으로 인식할 수 있다는 점이다. 그리고 어차피 우리는 붓을 올리고 내리는것에만 관심이 있음으로, 회전하는 횟수는 카운트 하지 않고 Board에서 1값만 fllow 하면 되는 것이다.
#include <iostream>
#include <vector>
using namespace std;
int dx[] = {1,0,-1,0};
int dy[] = {0,-1,0,1};
int board[2001][2001];
void DFS(int y, int x) {
board[y][x] = false;
int idx = 0;
for (idx = 0; idx < 4; ++idx) {
int n_y = y + loc[idx][0];
int n_x = x + loc[idx][1];
if (n_y >= 0 && n_y <= 2000 && n_x >= 0 && n_x <= 2000)
{
if (board[n_y][n_x])
{
DFS(n_y, n_x);
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int N = 0;
int idx = 0;
cin >> N;
int x1 = 0, x2 = 0, y1 = 0, y2 = 0;
int y = 0, x = 0;
for (idx = 0; idx < N; ++idx) {
cin >> x1 >> y1 >> x2 >> y2;
x1 = (x1 + 500) * 2;
x2 = (x2 + 500) * 2;
y1 = (y1 + 500) * 2;
y2 = (y2 + 500) * 2;
for (x = x1; x <= x2; ++x) {
board[y1][x] = 1;
board[y2][x] = 1;
}
for (y = y1; y <= y2; ++y) {
board[y][x1] = 1;
board[y][x2] = 1;
}
}
int answer = 0;
if (board[1000][1000] == 1) answer = -1;
for (y = 0; y <= 2000; ++y) {
for (x = 0; x <= 2000; ++x) {
if (board[y][x]) {
++answer;
DFS(y, x);
}
}
}
cout << answer;
}