[Algorithm/C++17] 백준 15685 드래곤 커브

문제

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

15685번: 드래곤 커브

풀이 방법

처음의 대략적인 생각은 다음과 같다.

1. 시작점 좌표와 두 번째 좌표를 리스트에 넣는다.
2. 3~4를 세대 g만큼 반복한다.
3. 끝점 기준으로 기존 좌표들을 회전시켜 새로운 좌표를 만든다. (회전은 회전행렬을 사용한다.)
4. 만들어진 좌표를 리스트에 넣는다.
5. 리스트를 순회하면서 2차원 배열에 점을 찍고 그 점이 사각형을 이루는지 검사한다.

회전행렬에 대해서 인터넷을 찾아보던 중 더욱 간단한 풀이를 찾았다.

위의 방법대로 해도 풀리긴 하지만 문제에서의 y좌표가 아래로 갈수록 커지는 것만 주의하면 된다.

간단한 풀이는 다음과 같다.

1. 시작 방향을 리스트에 넣는다.
2. 리스트 마지막부터 처음까지, 방향을 회전시켜 리스트에 넣는다.이를 g만큼 반복한다. 이렇게 하면 시작점부터 끝점까지의 방향이 리스트에 저장되어있을 것이다.
3. 리스트를 순회하며 저장된 방향대로 시작점부터 좌표를 움직여 2차원배열에 점을 찍는다.
4. 2차원 배열에서 사각형으로 이루어진 점을 검사한다.

코드

#include <cstdio>
#include <vector>
using namespace std;
int dx[] = {1,0,-1,0};
int dy[] = {0,-1,0,1};
int main()
{
    int n;
    scanf("%d", &n);
    vector<vector<int>> board(102, vector<int>(102,0));
    vector<int> curve;
    int x, y, d, g;
    for(int i=0; i<n; i++)
    {
        scanf("%d %d %d %d", &x, &y, &d, &g);
        curve.push_back(d);
        /* dragon curve */
        // 방향
        for(int j=0; j<g; j++)
        {
            int idx = curve.size()-1;
            for(int k=idx; k>=0; k--)
                curve.push_back((curve[k]+1)%4);
        }
        // 좌표
        board[y][x] = 1;
        for(int j=0; j<curve.size(); j++)
        {
            x += dx[curve[j]];
            y += dy[curve[j]];
            board[y][x] = 1;
        }
        curve.clear();
    }
    // 사각형 검사
    int answer = 0;
    for(int i=0; i<=100; i++)
    {
        for(int j=0; j<=100; j++)
        {
            if(board[i][j] > 0 && board[i][j+1] > 0 && board[i+1][j]>0 && board[i+1][j+1] > 0)
                answer++;
        }
    }
    printf("%d", answer);
    return 0;
}

고찰

방향만 저장해놓고 시작점을 따라 그대로 시뮬레이션해주면 됐던 문제다.

회전 행렬을 사용한 풀이 방법은 잘 생각했지만 굳이 어렵게 안해도 쉽게 풀 수 있는 방법이 있었다.