[JAVA] 백준 드래곤 커브

문제의 핵심은 두가지이다.

1. 커브의 규칙성을 알아내서 구현하는 방법
2. 세대에 도달하기까지 반복하기.

2번을 이해하지 못했다.

Input값에는 x,y,d,g가 있는데 여기서 입력받는 g가 어떤용도로 사용되는지 명확한 느낌이 안들었다.

 

처음에 필자는 Input으로 주어진것은 좌표위에 일부 드래곤 커브만 주어진거라고 생각했다.

 

하지만, 여기서 주어진 g의 의미는 아래와 같다.

• x,y좌표에서 시작하는 방향(d)로 주어진다.
• 위의 값은 0세대이다.
• 따라서 0세대에서 주어진 g세대까지 확장시켜나가라는 뜻이다.

예제 1을 g세대까지 확장시키면 이렇게 나온다.

예제 1

3

3 3 0 1

4 2 1 3

4 2 2 1

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

class Main {
    static boolean[][] map = new boolean[101][101];
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int ans = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            StringTokenizer 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());   // 세대

            dragonCurve(x, y, d, g);

        }

        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                if (map[i][j] && map[i][j + 1] && map[i + 1][j] && map[i + 1][j + 1]) {
                    ans++;
                }
            }
        }

        bw.write(ans + "\n");
        br.close();
        bw.flush();
        bw.close();
    }

    public static void dragonCurve(int x, int y, int d, int g) {
        List<Integer> d_list = new ArrayList<>();
        d_list.add(d);

        for (int i = 1; i <= g; i++) {
            for (int j = d_list.size() - 1; j >= 0; j--) {
                d_list.add((d_list.get(j) + 1) % 4);
            }
        }

        map[y][x] = true;
        for (Integer direction : d_list) {
            x += dx[direction];
            y += dy[direction];
            map[y][x] = true;
        }
    }
}