[c++] BOJ 3108 :: 로고

문제

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

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

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

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

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

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

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

 

풀이

• 처음에 받은 사각형 모두 1로 칠하기
• dfs 돌면서 값이 1이면 2로 만드는 코드 실행
  • 좌표상으로는 -500까지 이동할 수 있으므로 배열로 표현하기 위해 500을 더해줘야 함
  • dfs 돌려면 바로 옆에 있는 점으로 이동하지 않기 위해 위치에 곱하기 2해주어야 함
• 값이 0이거나 2면 (사각형이 아니거나, 들른 사각형이면) 건너뛰기
• 한 번 loop 돌 때마다 한 붓으로 그린다고 생각하여 result 늘려주기
• (0, 0)에서 연필을 내리고 있으므로 (0, 0)에 들른 적이 있으면 result-1 필요

 

코드

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <unordered_set>

using namespace std;

int N;
int map[2001][2001];
int groupNum = 0;
int result = 0;
int direction[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };

void checkMap(int minX, int maxX, int minY, int maxY, int group) { // O(n)
    // 사각형 둘레 체크하는 함수
    for (int j = minY; j <= maxY; j++) {
        map[maxX][j] = group;
        map[minX][j] = group;
    }
    for (int i = minX; i <= maxX; i++) {
        map[i][minY] = group;
        map[i][maxY] = group;
    }
}

void visitMap(int r, int c) { // dfs
    if (map[r][c] == 0 || map[r][c] == 2) return; // 안 들러도 되거나 이미 들렀으면 패스
    map[r][c] = 2;

    for (int i = 0; i < 4; i++) {
        int newR = direction[i][0] + r;
        int newC = direction[i][1] + c;

        if (newR < 0 || newC < 0 || newR > 2000 || newC > 2000) continue;
        visitMap(newR, newC);
    }
}


int main() {
    cin >> N;
    fill(&map[0][0], &map[2000][2001], 0);
    for (int i = 0; i < N; i++) { // O(n^2)
        int x, y, x2, y2;
        cin >> x >> y >> x2 >> y2;
        checkMap((x + 500) * 2, (x2 + 500) * 2, (y + 500) * 2, (y2 + 500) * 2, 1); // *2 + 500
    }

    for (int i = 0; i < 2001; i++) {
        for (int j = 0; j < 2001; j++) { // 10^6
            if (map[i][j] == 1) {
                visitMap(i, j);
                result++;
            }
        }
    }

    if (map[1000][1000] != 0) { // (0, 0)에서 시작하는게 있으면 -1
        result--;
    }
    cout << result;
    cin >> N;
}

 

 

결과

문제	메모리	시간	코드 길이
gmldms784	19280	20	1422