BOJ 15685 드래곤 커브 [Java]

BOJ 15685 드래곤 커브

1. 문제 보기

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

2. 문제 해설

구현 문제다. 구현 문제는 내가 구현해야할 기능이 무엇인가를 파악하면 풀이의 방향이 보인다. 이 문제는 2가지 기능을 구현해주면 된다.
첫번째는 드래곤 커브를 그리는 기능, 두번째는 그린 후 크기가 1×1 인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 파악하는 기능이다. 두 기능을 구현해보자.

1. 드래곤 커브를 그리는 메서드 - drawDragonCurve 메서드
이 메서드를 구현하는 것이 상당히 어려웠다. 정확히 말하자면 구현이 어려웠다기보다는 드래곤 커브가 세대가 늘어날 때 추가되는 선의 규칙을 찾는 과정이 쉽지가 않았다. 세대가 늘어날때 드래곤 커브의 선의 방향이 어떻게 되는지 한번 알아보자.

0세대 - (0)
1세대 - (0)(1)
2세대 - (0 1)(2 1)
3세대 - (0 1 2 1)(2 3 2 1)
.
.
.
이렇게 차근차근 세대별로 써보면 규칙이 보인다. 세대가 늘어날 때 추가되는 선의 방향은 이전 세대의 방향을 거꾸로 한 후 +1씩 해주면 된다.
규칙을 알았다면 아래 코드의 38~56줄과 같이 쉽게 구현해줄 수 있다.

2. 크기가 1×1 인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 파악하는 메서드 - checkSquare 메서드
정말 간단하다. 격자의 범위가 0~100이니 전부를 돌면서 탐색해주면 된다.

3. 코드 보기

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

public class Main {
    static int n, x, y, d, g;
    static boolean[][] map;
    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));

        n = Integer.parseInt(br.readLine());
        map = new boolean[101][101];

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

            drawDragonCurve(x, y, d, g);
        }

        checkSquare();

        bw.write(Integer.toString(ans));
        br.close();
        bw.flush();
        bw.close();
    }

    static void drawDragonCurve(int x, int y, int d, int g) { // 드래곤 커브를 그림
        List<Integer> direction = new ArrayList<>();
        direction.add(d); // 0세대 방향 추가

        for (int i = 1; i < g + 1; i++) { // 방향 추가
            for (int j = direction.size() - 1; j >= 0; j--) {
                direction.add((direction.get(j) + 1) % 4);
            }
        }

        map[y][x] = true; // 시작점 그리기

        for (int dir : direction) { // 담겨진 방향에 맞게 그리기
            x += dx[dir];
            y += dy[dir];

            map[y][x] = true;
        }
    }

    static void checkSquare() { // 격자에서 1x1 정사각형의 네 꼭짓점이 모두 드래곤 커브에 속하는 것의 갯수를 구함
        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++;
                }
            }
        }
    }
}