백준 15685번 - 드래곤 커브

www.acmicpc.net/problem/15685

15685번: 드래곤 커브

구현과 시뮬레이션, 삼성 코테의 전형적인 유형이다.

 

설명은 복잡하고 어려워 보이지만 사실 풀어써보면 굉장히 간단한 문제다.

 

1. 0세대는 지정된 방향으로 한 칸 전진

2. 1세대 이상부터는 지금까지의 선분들을 끝점을 기준으로 모두 90도 회전

 

여기서 선분이라고 생각하지 않고 선분의 각 끝점이라고 생각해보면 어렵지 않다.

 

그럼 90도 회전은 어떻게 시켜야 하나 고민해봐야 한다.

 

나는 이 문제를 보고 90도 회전은 반드시 간단한 수식 하나로 나올 것이라고 생각했다.

 

그래서 가장 단순하고도 좋은 방법인 노가다를 통해 수식을 구했다.

 

한 점을 기준점을 기준으로 90도 회전시키는 수식

(해당 점의 좌표 - 기준점)  ->  x와 y좌표를 바꾸고 x에 -1 곱하기  ->  다시 기준점 더해주기

 

어떤 원리인지는.. 넘어가자^^

 

그럼 이제 생각해보면 당연히 재귀함수를 떠올리겠지만 난 재귀 함수를 싫어하기 때문에 간단한 반복문으로 코드를 짰다ㅎㅎ

 

여기서 가장 핵심은 끝점을 어떻게 판단할 것이냐이다.

 

그림을 열심히 그려보면 끝점은 반드시 시작점이 회전한 점임을 알 수 있다.

 

그렇기 때문에 새롭게 그려지는 점들을 차례로 vector에 넣는다고 했을 때, 시작점을 가장 마지막에 회전시키면 된다.

 

(설명이 살짝 복잡할 수 있으나 코드에 자세히 주석을 달아놓았습니다.)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
 
bool check[107][107];
int dx[] = { 1, 0, -1, 0};
int dy[] = { 0, -1, 0, 1};
 
void draw(int x, int y, int d, int g) {
    // 지금까지 저장된 모든 좌표를 끝점을 기준으로
    // 시계방향으로 90도 꺽은점들 check하기
    vector<pii>point;
    point.push_back(pii(x, y)); // 시작점 push
    point.push_back(pii(x + dx[d], y + dy[d])); // 0세대
    int t = 0;
    while (t < g) { // 0세대 이상일 때에는
        t++;
        // 끝점(반드시 vector의 마지막 점임)을 제외하고 모두 커브 돌리기
        int size = point.size() - 1;
        int xx = point.back().first; // 기준점 x좌표
        int yy = point.back().second; // 기준점 y좌표
        for (int i = size -1 ; i >= 0; i--) { // 반드시 역순으로 해야됨. 끝점은 시작점을 회전시킨 점이기 때문!
            // 회전시킨 좌표 = (원래 좌표 - 기준점) -> 규칙 -> + 기준점
            // 이때 규칙 = x좌표와 y좌표 뒤집고 x에만 음수화
            int nx = point[i].first - xx;
            int ny = point[i].second - yy;
            swap(nx, ny); nx *= -1; // 규칙 실행
            nx += xx; ny += yy;
            point.push_back(pii(nx, ny));
        }
    }
    // 모든 점들을 체크하기
    for (int i = 0; i < point.size(); i++) {
        int tx = point[i].first;
        int ty = point[i].second;
        if (0 <= tx && tx <= 100 && 0 <= ty && ty <= 100 && check[tx][ty] == false) {
            check[tx][ty] = true;
        }
    }
    
}
 
int solve() {
    int ret = 0;
    // 네 꼭짓점 모두 확인하는 함수
    for (int i = 0; i <= 100; i++) {
        for (int j = 0; j <= 100; j++) {
            if (check[i][j] && check[i + 1][j] && check[i][j + 1] && check[i + 1][j + 1]) ret++;
        }
    }
    return ret;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, x, y, d, g;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x >> y >> d >> g;
        draw(x, y, d, g);
    }
    cout << solve() << "\n";
}

정사각형의 네 꼭짓점이 모두 드래곤 커브 안에 포함되어있는지 확인하는 방법은 solve() 함수를 확인해보면 된다.

 

나름 깔끔한 문제였던 것 같다