[백준 - G4] 15685. 드래곤 커브

문제

이 문제는 문제에서 주어진 규칙 그대로 드래곤 커브를 격자 위에 그려보는 구현 문제이다.

드래곤 커브가 여러 개 주어지며, 모든 커브를 격자에 그린 뒤 1×1 크기의 정사각형 중 네 꼭짓점이 모두 드래곤 커브에 포함되는 개수를 세는 것이 목표다.

 

 

1. 방향 리스트로 드래곤 커브 표현하기

드래곤 커브의 핵심은 방향의 나열이다. 선을 직접 회전시키는 대신, 이동 방향을 리스트로 관리하면 훨씬 간단하게 구현할 수 있다.

• 0세대 드래곤 커브는 시작 방향 d 하나로 구성된다.
• 이후 세대는 이전 세대의 방향 리스트를 이용해 생성한다.

세대를 확장하는 규칙은 다음과 같다.

이전 세대의 방향 리스트를 뒤에서부터 탐색하면서,
각 방향을 시계 방향으로 90도 회전한 값을 리스트 뒤에 추가한다.
(시계 회전은 (dir + 1) % 4로 표현 가능)

이 과정을 g세대까지 반복하면, 해당 드래곤 커브의 전체 방향 리스트가 완성된다.

 

 

 

2. 방향 리스트로 드래곤 커브 표현하기

방향 리스트가 완성되면, 이를 이용해 드래곤 커브를 실제로 격자 위에 그린다.

1. 시작 좌표 (x, y)를 먼저 격자에 표시한다.
2. 방향 리스트를 앞에서부터 하나씩 따라가며 좌표를 이동한다.
3. 이동하면서 도착한 모든 좌표를 격자에 표시한다.

격자는 좌표 범위가 최대 0 ≤ x, y ≤ 100이므로
boolean[101][101] 배열을 사용해 드래곤 커브가 지나간 점을 기록한다.

이렇게 하면 여러 드래곤 커브가 겹치더라도
중복 처리에 대한 추가 로직 없이 간단하게 관리할 수 있다.

 

 

3. 1×1 정사각형 개수 세기

격자의 모든 좌표 (x, y)에 대해 다음 네 점을 확인한다.

(x, y), (x+1, y), (x, y+1), (x+1, y+1)

이 네 꼭짓점이 모두 드래곤 커브의 일부라면
해당 위치에 1×1 정사각형이 하나 존재하는 것으로 판단하고 카운트한다.

 

제출 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int N;
    static HashSet<Node> nodes;
    static boolean[][] map;

    static class Node {
        int x, y;

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

        @Override
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (!(o instanceof Node))
                return false;
            Node n = (Node) o;
            return x == n.x && y == n.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }

    }

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        nodes = new HashSet<>();
        map = new boolean[101][101];
        for (int i = 0; i < N; i++) {
            String[] split = br.readLine().split(" ");
            int x = Integer.parseInt(split[0]);
            int y = Integer.parseInt(split[1]);
            int d = Integer.parseInt(split[2]);
            int g = Integer.parseInt(split[3]);

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

        for (Node node : nodes) {
            map[node.x][node.y] = true;
        }

        System.out.println(square());

    }

    static int square() {

        int cnt = 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]) {
                    cnt++;
                }
            }
        }

        return cnt;
    }

    static int[] dx = { 1, 0, -1, 0 };
    static int[] dy = { 0, -1, 0, 1 };

    static void move(int x, int y, int d, int g) {

        List<Integer> dirs = new ArrayList<Integer>();
        dirs.add(d);

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

        // System.out.println(dirs);
        // dirs의 좌표 이동
        map[x][y] = true;
        for (int dir : dirs) {
            x += dx[dir];
            y += dy[dir];

            nodes.add(new Node(x, y));
        }

    }

}

 

 

문제 링크

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