[BOJ] 15685. 드래곤커브 - Simulation

[BOJ] 15685. 드래곤커브 - Simulation

제출일 : 2019-10-19

문제 풀이 시간 : 3H

난이도 : ★★★★

Problem

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

Input

첫째 줄에 드래곤 커브의 개수 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좌표가 증가하는 방향 (↓)

Output

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

Example

input

3
3 3 0 1
4 2 1 3
4 2 2 1

output

4

Solution & Inpression

시뮬레이션 문제

시뮬레이션은 역시 어렵다.

90도 시계방향으로 회전하는 것을 벡터의 회전이라 생각했고

• x' = xcos(90)-ysin(90)
• y' = xsin(90)+ycos(90)

라는 공식에 의해 새로운 좌표는 x'=-y, y'=x가 된다.

또 문제를 풀때 기억해야 할 부분은 끝에 점이 붙는것과 붙은 선분은 시작점에서부터 먼점에 있는 선분부터 시작이라는것이다.

햇갈려....

Code

언어 : JAVA

메모리 : 14,984 kb

실행시간 : 124 ms

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static int N;
    static ArrayList<Dragon> list;
    static int[][] map = new int[101][101];

    static class Dragon {
        ArrayList<int[]> point;

        public Dragon(int[] p, int dir, int g) {
            this.point = new ArrayList<>();
            this.point.add(p);
            if (dir == 0)
                this.point.add(new int[] { p[0], p[1] + 1 });
            else if (dir == 1)
                this.point.add(new int[] { p[0] - 1, p[1] });
            else if (dir == 2)
                this.point.add(new int[] { p[0], p[1] - 1 });
            else
                this.point.add(new int[] { p[0] + 1, p[1] });
            while (g-- != 0) {
                spin();
            }
        }

        void spin() {

            // x' = xcos(90)-ysin(90)
            // y' = xsin(90)+ycos(90)

            // sin(90) = 1;
            // cos(90) = 0;

            // x' = -y
            // y' = x
            int size = point.size();
            for (int i = size - 1; i > 0; i--) {
                int[] cen = point.get(i - 1);
                int[] cur = point.get(i);
                int[] end = point.get(point.size() - 1);

                int tx = cur[0] - cen[0];
                int ty = cur[1] - cen[1];

                int nx = end[0] - ty;
                int ny = end[1] + tx;

                point.add(new int[] { nx, ny });
            }

        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt(); // 드래곤 커브의 개수 N(1 ≤ N ≤ 20)
        list = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            int c = sc.nextInt();
            int r = sc.nextInt();
            list.add(new Dragon(new int[] { r, c }, sc.nextInt(), sc.nextInt()));
        }

        for (int i = 0; i < N; i++) {
            ArrayList<int[]> l = list.get(i).point;
            for (int j = 0; j < l.size(); j++) {
                map[l.get(j)[0]][l.get(j)[1]] = 1;
            }
        }

        int ans = 0;
        for (int i = 0; i < 101; i++) {
            for (int j = 0; j < 101; j++) {
                if (map[i][j] == 1)
                    if (check(i, j))
                        ans++;
            }
        }
        System.out.println(ans);
    }

    private static boolean check(int i, int j) {
        int[] dr = { 1, 0, 1 };
        int[] dc = { 0, 1, 1 };

        for (int k = 0; k < 3; k++) {
            int r = i + dr[k];
            int c = j + dc[k];
            if (!range(r, c)) {
                return false;
            } else {
                if (map[r][c] == 0) {
                    return false;
                }
            }
        }
        return true;
    }

    private static boolean range(int r, int c) {
        if (0 <= r && r < 101 && 0 <= c && c < 101)
            return true;
        return false;
    }
}