[BOJ] 15685:드래곤 커브

0. 문제

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

15685번: 드래곤 커브

 

 

1. 문제분석

- 드래곤 커브를 그리기 위해서는, 직전 세대에 커브 그리기를 마친 점에서부터 시작해서, 이전 세대에서 그린 커브와 동일한 모양의 커브를 시계방향으로 90도를 회전시켜 그려야 한다. 이 때, 새로운 커브를 그릴 때는 이전 세대에서 커브를 그렸던 순서의 역순으로 다시 그려야 한다. 따라서 LIFO(Last In First Out)의 구조인 스택을 응용하여 문제를 풀어야 한다. 

 

2. 주의할 점

- 만들 수 있는 1x1 정사각형의 개수를 셀 때 그려진 '선'이 기준이 아니라 '점'이 기준이다. 즉, 하나의 정사각형 위치에 3변만 그려져있더라도 하나의 정사각형을 만들 수 있는 조건을 만족하는 것이다.

- 90도를 돌렸을 때의 방향이 어떻게 변화하는지 체크해야 한다.

- 드래곤 커브를 그릴 때, 꼭 모든 '선'의 정보를 가지고 가야할 필요는 없다.

 

3. 소스코드(Java)

// boj 15683 드래곤 커브
// stack

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj_15685 {
    static int n;
    static boolean[][] isDotted = new boolean[100+1][100+1]; // isDotted[y][x]
    static int[] dy = {0,-1,0,1};
    static int[] dx = {1,0,-1,0};
    // direction change
    // 0 1 2 3 -> 1 2 3 0

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = stoi(st.nextToken());
        for (int i = 0; i < n; ++i) {
            st = new StringTokenizer(br.readLine());
            draw(stoi(st.nextToken()), stoi(st.nextToken()),
                    stoi(st.nextToken()), stoi(st.nextToken()));
        }
        System.out.print(count());
    }
    public static int stoi(String s) {return Integer.parseInt(s);}
    public static void draw(int x, int y, int d, int g) {
        int ny = y + dy[d], nx = x + dx[d];
        int[] dirs = new int [1];
        isDotted[y][x] = true;
        isDotted[ny][nx] = true;
        dirs[0] = d;
        for (int i = 1; i <= g; ++i) {
            int[] tmpDirs = new int [dirs.length * 2];
            for (int j = 0; j < dirs.length; ++j) {
                int nd = (dirs[j] + 1) % 4;
                ny += dy[nd];
                nx += dx[nd];
                isDotted[ny][nx] = true;
                tmpDirs[j + dirs.length] = dirs[j];
                tmpDirs[dirs.length - j - 1] = nd;
            }
            dirs = tmpDirs;
        }
    }
    public static int count() {
        int ret = 0;
        for (int i = 0; i < 100; ++i) {
            for (int j = 0; j < 100; ++j) {
                if (!isDotted[i][j]) continue;
                if (isDotted[i+1][j] && isDotted[i][j+1] && isDotted[i+1][j+1])
                    ret++;
            }
        }
        return ret;
    }

}

 

4. 여담

- 예전에 알고리즘 문제 해결전략 책 보면서 살짝 스치고 지나갔던 똑같은 문제가 있던 거 같은데 그 문제는 기억이 잘 안난다. 나중에 찾아봐야지.