[백준] 15685 드래곤 커브

문제 주소 : www.acmicpc.net/problem/15685

15685번: 드래곤 커브

문제 확인

 

간단한 시뮬레이션 문제입니다. 주어진대로 드래곤 커브 정보를 배열에 입력해둔 후 마지막에 정사각형 개수를 세면 됩니다.

 

풀이

 

드래곤 커브의 방향을 기록해야 다음 레벨의 드래곤 커브를 만들 수 있으므로 스택을 이용해서 기록합니다. 주의해야 할 점은 이전 단계 끝 지점에서 90도 방향으로 돌려야 하므로 스택에 저장된 정보를 top -> 0 순으로 읽어야 하며 모양이 90도 회전이므로 방향은 반시계 방향이 되어야 합니다.

* stack[top + 1] = (stack[top] + 1)%4, stack[top + 2] = (stack[top - 1] + 1)%4 ... 

같은 색으로 묶어보면 다음 방향은 반시계 방향

또한 드래곤 커브의 개수는 레벨에 따라 지정되며 2^level 개입니다. 이를 통해 스택에 방향을 저장해나갑니다.

코드

#include<cstdio>
int main() {
    char a[101][101] = { 0 }, dy[] = { 1,0,-1,0 }, dx[] = { 0,-1,0,1 };//왼상오하
    int n, c = 0;
    scanf("%d", &n);
    for (int i = 0, x, y, d, g; i < n; i++) {
        scanf("%d%d%d%d", &y, &x, &d, &g);
        a[x][y] = 1;
        x += dx[d]; y += dy[d];
        a[x][y] = 1;
        char s[1024] = { d };
        for (int t = 0, c = 1; t < g; t++, c <<= 1) {//c : 레벨에서 드래곤 커브 개수 0: 1개, 1: 2개, 2: 4개 ...
            for (int j = 0; j < c; j++) {//c를 기준으로 대칭으로 기록
                d = s[c + j] = (s[c - j - 1] + 1) % 4;//top -> 0 순으로, 90도 회전 = 반시계
                x += dx[d]; y += dy[d];
                a[x][y] = 1;//방문 표시
            }
        }
    }
    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < 100; j++) {
            if (a[i][j] && a[i][j + 1] && a[i + 1][j] && a[i + 1][j + 1])//계산
                c++;
        }
    }
    printf("%d", c);
}