[백준문제풀이] 3108 로고

 

풀이일시 : 2020-11-17

​

 

문제 :

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

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

제일 처음에 거북이는 (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)는 그 점의 대각선 방향의 반대 꼭짓점의 좌표이다.

ex)

5

1 1 4 4

3 3 6 6

4 4 5 5

5 0 8 3

6 1 7 2

​

 

출력 :

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

ex)

2

​

​

풀이 :

한붓그리기 문제의 분류로 볼 수 있다. DFS로 풀이

-> FD LT RT 등등을 직접 구현하려 하지 말고 dfs에서 사방을 탐색하며 나아가며 PD의 횟수만 구하면 된다.

​

좌표가 음수도 포함하므로 배열로 방문여부 표시불가하다.

-> 500을 더하는 방식 으로 겹치지 않는 직사각형을 방문할 여부가 있다.

-> 500을 더하고 2를 곱해준다. (모눈종이처럼 색을칠하기위해 한칸씩 더 만들어줌)

-> 직사각형의 각 점을 하나씩 방문했다는 값(2)으로 변경해준다.

​

주의 : 맨 처음시작할때 0,0에서 펜을 한번 내렸으므로 1000,1000방문했다면 1빼주자

 

#include <iostream>
#include <vector>
#include <queue>
#define MAX 2001

using namespace std;

int MAP[MAX][MAX]; //마이너스값이 들어갈수없기때문에 (MAP[-1][-1] ??)
bool visit[MAX][MAX];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

void dfs(int y, int x) {
	if (y < 0 || x < 0 || x >= MAX || y >= MAX) //범위가아니면
		return;
	if (MAP[y][x] == 2 || MAP[y][x] == 0) //dfs종료의 조건
		//MAP이 1이 아니고 2(이미dfs를거쳤다) 0(아무것도없다)
		return;
	MAP[y][x] = 2; //dfs방문처리해준다.
	for (int i = 0; i < 4; i++) { //방향을 모두탐색하여 dfs해준다.
		int nx = x + dx[i];
		int ny = y + dy[i];
		dfs(ny, nx);
	}
}

void solution() {
	int cnt;
	cnt = 0;
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			if (MAP[i][j] == 1) { //탐색하다가 드디어 칠해져있는 곳을 만났다면
				dfs(i, j); //dfs를 하고 
				cnt++; //한붓그리기 종료되었으므로 ++해준다.
			}
		}
	}
	if (MAP[1000][1000] == 2) //1000 , 1000 이라는것은 즉 0,0이다.
		cnt--; //0,0거쳤다면 cnt를 하나 줄여준다. 이미 시작할때 펜을 내렸었기때문
	cout << cnt << endl;
}

int main() {
	int N;
	int x1, y1, x2, y2;
	cin >> N;
	//입력받는 부분이 중요할것
	//한붓그리기와 동일

	for (int i = 0; i < N; i++) {
		cin >> x1 >> y1 >> x2 >> y2;
        //MAP 배열을 전부 양수로 늘려놨기때문에 입력 x,y도 바꿔서 입력해준다.
		x1 = (x1 + 500) * 2;
		y1 = (y1 + 500) * 2;
		x2 = (x2 + 500) * 2;
		y2 = (y2 + 500) * 2;
		for (int i = x1; i <= x2; i++) {
			MAP[y1][i] = 1;
			MAP[y2][i] = 1;
		}
		for (int i = y1; i <= y2; i++) {
			MAP[i][x1] = 1;
			MAP[i][x2] = 1;
		}
	}
	solution();

	return 0;
}