백준 15685 [자바] java 드래곤 커브

문제 링크: https://www.acmicpc.net/problem/15685

15685번: 드래곤 커브

 

▶문제

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

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

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

1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.

2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다. (파란색 선분은 새로 추가된 선분을 나타낸다)

3세대 드래곤 커브도 2세대 드래곤 커브를 이용해 만들 수 있다. 아래 그림은 3세대 드래곤 커브이다.

즉, K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다.

크기가 100×100인 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오. 격자의 좌표는 (x, y)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표이다.

---

▶입력

첫째 줄에 드래곤 커브의 개수 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인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.

---

▶해설

드래곤 커브가 주어질 때마다 map에 그리면서 최종적인 map에서 정사각형의 개수를 구하려고 했습니다.

 

1세대가 걸칠 때마다 시계 방향으로 90도 회전하고, 똑같은 모양을 그리는 것입니다. 그래서 지금까지 모양을 그렸던 방향을 저장하는 list를 만들었습니다. 

 

list의 활용은 최근의 그린 방향부터 오래된 방향을 순서 (d+1)%4를 해주면 끝점에서 시작하는 90도를 돌리고, 같은 모양이 그려집니다. (문제의 힌트와 그림에서 확인하실 수 있습니다.)

 

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

public class Main {

    static int n;
    static int[] xm = {1, 0, -1, 0}, ym = {0, -1, 0, 1};  // 0= 오른쪽 1=위쪽 2=왼쪽 3=아래쪽
    static boolean[][] map;

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

        map = new boolean[101][101];
        for (int i = 0; i < n; i++) {
            String[] s = br.readLine().split(" ");
            int x = Integer.parseInt(s[0]);
            int y = Integer.parseInt(s[1]);
            int d = Integer.parseInt(s[2]);
            int g = Integer.parseInt(s[3]);
            solve(x, y, d, g);
        }

        int result = findBox();
        System.out.println(result);
    }

    public static void solve(int x, int y, int d, int g) {
        List<Integer> list = new ArrayList<>();
        list.add(d);
        for(int i=1; i<=g; i++){
            for(int j=list.size()-1; j>=0; j--){
                list.add((list.get(j)+1)%4);
            }
        }
        map[y][x]=true;
        for(Integer dir: list){
            y+=ym[dir];
            x+=xm[dir];
            map[y][x]=true;
        }
    }
    public static int findBox(){
        int result=0;
        for(int i=0; i<100; i++){
            for(int j=0; j<100; j++){
                if(visitDot(i,j)){
                    result++;
                }
            }
        }
        return result;
    }
    public static boolean visitDot(int i, int j){
        if(map[i][j] && map[i+1][j] && map[i][j+1] && map[i+1][j+1]){
            return true;
        }
        else{
            return false;
        }
    }
}