[백준 15685] 드래곤 커브(Java)

문제 링크 : https://www.acmicpc.net/problem/15685

이 문제는 드래곤 커브 작성의 규칙성을 찾아내면 풀 수 있습니다.

이 문제의 가장 어려운 부분이 바로 드래곤 커브의 규칙성을 찾아내는 것인데요, 각 케이스 별로 나눠보면 다음과 같습니다.

(기존 / 신규)
1. 1세대 : 0 / 1
2. 2세대 : 0,1 / 2,1
3. 3세대 : 0,1,2,1 / 2,3,2,1
...

위의 수열을 확인해보면 새롭게 추가되는 드래곤 커브의 경우 기존 세대의 방향의 역순의 +1 이 된다는 것을 확인할 수 있습니다. 여기서 하나 더 유의할 점은 방향값이 3을 초과할 경우 다시 0으로 회귀하는 성질을 가지고 있기 때문에 (기존 세대의 방향의 역순의 +1)%4 라는 공식을 얻을 수 있습니다.

해당 정보를 토대로 0세대부터 g세대까지 모든 점을 체크하여 구현하시면 됩니다.

다음은 코드입니다.

import java.util.*;
import java.io.*;

public class Main{

    static int N;
    static int res = 0;
    static boolean[][] req = new boolean[101][101];
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,-1,0,1};

    static void checkSquare(){
        for(int i=0;i<100;i++){
            for(int j=0;j<100;j++){
                boolean a = req[i][j];
                boolean b = req[i+1][j];
                boolean c = req[i+1][j+1];
                boolean d = req[i][j+1];

                if(a && b && c && d) res++;
            }
        }
    }

    static void draw(int x, int y, int d, int g){
        // 현재 위치 체크
        req[y][x] = true;

        // 방향 저장
        ArrayList<Integer> direction = new ArrayList<>();

        // 현재 방향이 가리키는 끝점 체크
        int nx = x + dx[d];
        int ny = y + dy[d];
        req[ny][nx] = true;

        // 현재 방향 배열이 저장
        direction.add(d);

        // 세대를 진행하면서 이에 따른 방향의 끝값 체크
        // 새로운 세대 방향 설정 규칙
        // 기존 세대의 방향의 역순의 +1
        while(g-- >0){
            // 방향의 역순
            for(int i=direction.size()-1;i>=0;i--){
                // 새로운 세대 방향 = 기존 세대 방향의 역순의 +1
                // 이 때 방향이 3에서 0으로 넘어가므로 4의 나머지로 처리해주어야 함
                int nd = (direction.get(i)+1)%4;
                nx = nx + dx[nd];
                ny = ny + dy[nd];
                req[ny][nx] = true;
                direction.add(nd);
            }
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int g = Integer.parseInt(st.nextToken());
            draw(x,y,d,g);
        }

        checkSquare();
        System.out.println(res);
    }
}