[알고리즘, BOJ] 15685 드래곤 커브 - java

문제

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.

1. 시작 점
2. 시작 방향
3. 세대

0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다. (생략...)

입력

첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10)

입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다.

방향은 0, 1, 2, 3 중 하나이고, 다음을 의미한다.

• 0: x좌표가 증가하는 방향 (→)
• 1: y좌표가 감소하는 방향 (↑)
• 2: x좌표가 감소하는 방향 (←)
• 3: y좌표가 증가하는 방향 (↓)

출력

첫째 줄에 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.

풀이

"점" 관점에서 생각하다가 실패했다. 관점을 "방향"으로 옮겨보자. 문제가 굉장히 간단해진다.

 

방향 리스트 구하기

선의 길이는 어처피 1이므로 방향만 기억하고 있다가 순서대로 돌려주면 된다.

ArrayList<Integer> arr = new ArrayList<Integer>();
arr.add(d);
while (g-- > 0) {

    for (int j = arr.size() - 1; j >= 0; j--) {
        int direction = arr.get(j);
        arr.add((direction + 1) % 4);
    }
}

지도에 표시하기

순서대로 모든 방향을 구했다면 101 X 101 크기의 지도에 전부 표시한다.

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

사각형을 만드는 케이스 조사하기

모든 드래곤 커브를 지도에 표시했다면 브루트포스로 1 X 1 사각형이 만들어진 경우를 조사하자.

int result = 0;
for (int y = 0; y < 100; y++) {
    for (int x = 0; x < 100; x++) {
        if (map[y][x] > 0 &&
                map[y + 1][x] > 0 &&
                map[y][x + 1] > 0 &&
                map[y + 1][x + 1] > 0) {
            result++;
        }
    }
}

전체 코드

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

public class Main {

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

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

        int[][] map = new int[101][101];
        // 점이 아니라 방향을 기억할 것. 어처피 1만큼 움직이니까
        int N = Integer.parseInt(br.readLine());
        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 d = Integer.parseInt(st.nextToken());
            int g = Integer.parseInt(st.nextToken());

            ArrayList<Integer> arr = new ArrayList<Integer>();
            arr.add(d);
            while (g-- > 0) {

                for (int j = arr.size() - 1; j >= 0; j--) {
                    int direction = arr.get(j);
                    arr.add((direction + 1) % 4);
                }
            }

            // System.out.println(arr);

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

        int result = 0;
        for (int y = 0; y < 100; y++) {
            for (int x = 0; x < 100; x++) {
                if (map[y][x] > 0 &&
                        map[y + 1][x] > 0 &&
                        map[y][x + 1] > 0 &&
                        map[y + 1][x + 1] > 0) {
                    result++;
                }
            }
        }

        System.out.println(result);
    }
}