BOJ_15685 : 드래곤 커브

👉 문제링크

---

---

🔸 문제 분석 🔸

• 좌표가 0부터 시작하는 101 x 101 격자판이 있다.
• N번의 드래곤 커브를 수행한 후에 한 격자의 네 꼭짓점이 모두 드래곤 커브에 포함 된 칸의 개수를 출력한다.
• 드래곤 커브란 세대를 걸칠 수록 이전 세대의 마지막 점을 기준으로 기존 커브 그림을 90도 시계방향으로 돌려 추가로 이어 그리는 것이다.

🔸 문제 풀이 🔸

• 단순 구현/시뮬레이션 문제이다. 세대를 반복 할 때, 이전 세대의 회전 정보가 필요하다. 따라서 회전 정보를 누적해서 저장해야 하는데, 그 크기는 2^세대 수이다.
• 세대를 반복 할 때마다 이전 회전 정보를 역순으로 조회해서 드래곤 커브를 계산하면 된다.
• 마지막으로 칸의 개수를 카운트 할 때는 왼쪽 위 꼭짓점을 기준으로 격자판의 범위를 벗어나지 않게 조회한다.

🔸 코드 🔸

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

public class Main {
    private static final int[] dx = {1, 0, -1, 0};
    private static final int[] dy = {0, -1, 0, 1};
    private static final int MAX = 100;
    private static boolean[][] board;
    private static int[] curves;

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

        int N = Integer.parseInt(br.readLine());
        board = new boolean[MAX + 1][MAX + 1];

        // Draw
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()); // 시작 col 좌표
            int y = Integer.parseInt(st.nextToken()); // 시작 row 좌표
            int d = Integer.parseInt(st.nextToken()); // 시작 방향
            int g = Integer.parseInt(st.nextToken()); // 드래곤 커브 세대의 수

            curves = new int[(int) Math.pow(2, g)];
            curves[0] = d;

            draw(y, x, g);
        }

        // Count
        int cnt = 0;
        for (int i = 0; i < MAX; i++) {
            for (int j = 0; j < MAX; j++) {
                if (board[i][j] && board[i][j + 1] && board[i + 1][j] && board[i + 1][j + 1]) {
                    cnt++;
                }
            }
        }
        // Output
        bw.write(Integer.toString(cnt));
        bw.flush();
    }

    private static void draw(int row, int col, int g) {
        int idx = 0;
        int d = curves[idx];
        board[row][col] = true;
        row += dy[d];
        col += dx[d];
        board[row][col] = true;

        for (int i = 1; i <= g; i++) { // 1 ~ g세대 계산
            for (int j = idx; j >= 0; j--) { // 역순으로 저장된 방향 확인
                d = (curves[j] + 1) % 4; // 새로운 방향
                curves[++idx] = d;
                row += dy[d];
                col += dx[d];
                board[row][col] = true;
            }
        }
    }
}

🔸 코드 해석 🔸

• 문제에서 제시 된 방향 정보(우상좌하)를 dx, dy 델타 정보로 저장해서 사용했다.
• 격자판의 각 칸이 드래곤 커브에 포함 되는지 boolean 2차원 배열 board에 저장했다.
• 누적 회전 정보를 int 배열 curves에 저장했다.
• draw() 메서드에서 드래곤 커브를 구현해 board에 표시했다.
  • 최초 0세대는 무조건 있으므로 시작 좌표와 다음 좌표를 board에 표시한다
  • 다음 1세대 부터는 도착하는 좌표만 board에 표시한다.
• 드래곤 커브를 모두 그린 후에 왼쪽위 꼭짓점을 기준으로 네 꼭짓점이 모두 true인 칸을 찾아 카운트하고 출력한다.

---

🔸 end 🔸

• 특별한 알고리즘이 없는 구현/시뮬레이션 문제여서 막힘없이 풀이를 떠올리긴 했다.
  • 하지만 고민 시간 자체가 오래 걸렸고, 디버깅도 더디게 디어서 2시간이 훌쩍 넘어서 풀었다.
  • 0번째 세대와 그 이후의 세대를 분리해서 생각하기까지가 가장 오래 걸린 것 같다.
  • 마우스도 없이 노트북 터치패드로 풀이해서 더 느려지고 집중력도 흐려진 것 같다.
• curves의 크기 계산을 2^세대수로 잘 계산해 놓고, 디버깅 과정에서 2^세대수+1로 늘려서 제출했다. 수정해서 다시 제출하느라 3번 제출해 보았다.
• 풀이 계획을 적어가며 풀이했다.