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

1. 문제설명

드래곤 커브는 시작 점(x, y)에서 주어진 방향으로 직선을 그린 후, 특정 규칙에 따라 회전하며 곡선을 만들어낸다. 방향(d)과 세대(g)가 주어지면, 해당 드래곤 커브를 그린 후, 그리는 과정에서 만들어지는 1x1 정사각형이 몇 개인지 구하는 문제이다.

(0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10)

드래곤 커브의 규칙은 주어진 방향으로 1세대 드래곤 커브를 그리고, 세대별로 현재까지 그린 선분들을 뒤집은 후 90도로 회전시킨 뒤, 이를 이어서 그리는 방식이다.

• 시간 제한: 1초
• 메모리 제한: 512MB

 

2. 접근 방식

참고: https://dublin-java.tistory.com/34

• 방향 전환 (90도)
  • 0 → 1, 1 → 2, 2 → 3, 3 → 0
  • 위를 식으로 전환하면 ⇒ (g + 1) % 4
  • 방향 정보를 리스트에 저장하여 반환.
• 드래곤 커브의 각 세대별 좌표를 계산하고 기록한다.
  • 방향 정보를 바턍으로 시작점부터 좌표를 기록한다.
  • 0 → x++, 1 → y--, 2 → x--, 3 → y++
• 1x1 크기의 정사각형을 확인한다.
  • 좌표 (x, y), (x+1, y), (x, y+1), (x+1, y+1)이 모두 커브에 포함되는 경우

 

3. 최종 코드

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

public class Main {
    static boolean[][] map = new boolean[101][101];

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

        while (n-- > 0) {
            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());

            List<Integer> directions = getDirections(d, g);
            draw(x, y, directions);
        }

        System.out.println(getCount());
    }

    static List<Integer> getDirections(int d, int g) {
        List<Integer> directions = new ArrayList<>(); // 방향 저장
        directions.add(d); // 초기 방향 입력

        while(g-- > 0) { // g세대까지 진행
            // "마지막 방향 -> 처음 방향" 순서로 진행
            for(int i=directions.size()-1; i>=0; i--) {
                // 새로운 방향 = (기존 d + 1) % 4
                int direction = (directions.get(i) + 1) % 4;
                directions.add(direction); // 새로운 방향 추가
            }
        }

        return directions;
    }

    static void draw(int x, int y, List<Integer> directions) {
        map[x][y] = true; // 시작점 체크

        for(int direction : directions) {
            if(direction == 0) map[++x][y] = true;
            else if(direction == 1) map[x][--y] = true;
            else if(direction == 2) map[--x][y] = true;
            else if(direction == 3) map[x][++y] = true;
        }
    }

    static int getCount() {
        int count = 0;

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

        return count;
    }
}