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

백준 15685번 드래곤 커브 : https://www.acmicpc.net/problem/15685

15685번: 드래곤 커브

 

 

입력으로 드래곤 커브의 정보가 주어지면 1 x 1의 정사각형 개수가 몇 개인지 판단하는 문제이다.

입력으로는 드래곤 커브의 시작 점, 시작 방향, 세대가 주어진다.

 

드래곤 커브는이전 세대에서 시계 방향으로 90도만큼 회전한 모양이 다음 세대가 된다.

따라서 다음 세대에 새로 생긴 선분들의 방향은 이전 세대 방향의 영향을 받는다.

 

문제에 주어진 예시를 보고 설명을 하자면,

세대 0

세대가 0인 드래곤 커브의 방향은 [0]이다.

세대 1

세대가 1인 아래의 선분의 방향은 [0, 1]이다.

세대 2

세대가 2인 드래곤 커브의 방향은 [0, 1, 2, 1]이다.

세대 3

마지막으로 세대가 3인 드래곤 커브의 방향은 [0, 1, 2, 1, 2, 3, 2, 1]이다.

 

아직 규칙이 보이지 않는다면 방향들의 정보를 절반씩 나눠서 새로 생긴 정보를 거꾸로 보면 이해가 될 것이다.

세대가 3인 드래곤 커브의 방향 정보는 기존에 있던 방향 정보인 [0, 1, 2, 1]과 새로 생긴 [2, 3, 2, 1]로 나눌 수 있다.

여기서 새로 생긴 정보를 역순으로 정렬해보면 [1, 2, 3, 2]가 된다.

규칙은 이전에 있던 방향 정보를 뒤에서부터 탐색하여 1씩 더해주면 된다.

 

구현에서는 ArrayList를 하나 선언하여 기존의 방향 정보들을 저장한 뒤,

세대를 1씩 증가시키면서 새로 생긴 방향 정보를 ArrayList에 추가로 더해줬다.

선분을 만들 때는 2차원 boolean 배열인 map에 체크를 해주었으며,

탐색을 마친 후에는 map에서 사각형을 만들 수 있는 위치를 count하여 반환해주었다.

 

 

총 걸린 시간 : 1시간 10분

난이도 : ★★☆☆☆

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    private static boolean[][] map = new boolean[101][101];
    private static int x1 = 100, x2 = 0, y1 = 100, y2 = 0; // 최대 범위 설정
    private static int[] dx = {0, -1, 0, 1};
    private static int[] dy = {1, 0, -1, 0};

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

        int n = Integer.parseInt(br.readLine());
        Node[] list = new Node[n];

        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 dir = Integer.parseInt(st.nextToken());
            int gen = Integer.parseInt(st.nextToken()); // 세대

            setRange(y, x);
            list[i] = new Node(y, x, dir, gen);
        }

        for (int i = 0; i < n; i++) {
            fill(list[i]);
        }
        int answer = countSquare();
        System.out.println(answer);
    }

    private static void fill(Node node) {
        int gen = node.gen;
        ArrayList<Integer> list = new ArrayList<>();
        map[node.x][node.y] = true;
        map[node.x + dx[node.dir]][node.y + dy[node.dir]] = true;
        list.add(node.dir);

        int x = node.x + dx[node.dir];
        int y = node.y + dy[node.dir];
        setRange(x, y);

        int ndir;
        while (gen-- > 0) {
            for (int i = list.size() - 1; i >= 0; i--) {
                ndir = (list.get(i) + 1) % 4;
                x = x + dx[ndir];
                y = y + dy[ndir];
                setRange(x, y);

                map[x][y] = true;
                list.add(ndir);
            }
        }
    }

    private static void setRange(int x, int y) {
        if (x < x1) x1 = x;
        if (x > x2) x2 = x;
        if (y < y1) y1 = y;
        if (y > y2) y2 = y;
    }

    private static int countSquare() { // 네모 몇개 있는지 count
        int count = 0;
        for (int i = x1; i < x2; i++) {
            for (int j = y1; j < y2; j++) {
                if (!map[i][j]) continue;
                if (map[i][j] && map[i + 1][j] && map[i][j + 1] && map[i + 1][j + 1]) count++;
            }
        }
        return count;
    }
}

class Node {
    int x, y;
    int dir;
    int gen;

    public Node(int x, int y, int dir, int gen) {
        this.x = x;
        this.y = y;
        this.dir = dir;
        this.gen = gen;
    }
}