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

🔗 15685번 : 드래곤 커브
● Java 풀이
● 시간 제한 1초
● 메모리 제한 512 MB

 

문제

 

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 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만 유효한 좌표이다.

 

풀이

import java.io.*;
import java.util.*;

public class Main {
    private static int N;  // 드래곤 커브의 개수 (1 <= N <= 20)
    private static boolean[][] dragonCurve;  // 방문 check
    private static List<Integer> dirList;  // 이동 방향 저장할 List
    private static final int[] dr = {0, -1, 0, 1}, dc = {1, 0, -1, 0};  // 방향 구분

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());  // 드래곤 커브 개수 받기
        dragonCurve = new boolean[101][101];  // 최대 Map 크기 초기화
        dirList = new ArrayList<>();  // 이동 방향 저장할 List 초기화

        StringTokenizer st;
        int x, y, d, g, nr, nc;
        for (int i = 1; i <= N; i++) {
            dirList.clear();  // 리스트 비우기 (이동 방향 0 스택)
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            d = Integer.parseInt(st.nextToken());
            g = Integer.parseInt(st.nextToken());

            // 0단계 드래곤 포스
            int[] lastPos = new int[]{y + dr[d], x + dc[d]};  // [0]: row(세로) 이동, [1]: col(가로) 이동
            //System.out.printf("(%d, %d)에서 (%d, %d)로 이동\n", y, x, nr, nc);
            //System.out.printf("0단계 완료\n\n");

            dragonCurve[y][x] = dragonCurve[lastPos[0]][lastPos[1]] = true;  // 0단계 드래곤 포스 방문 체크
            dirList.add(d);  // 방향 삽입
            for (int j = 0; j < g; j++) {  // 드래곤커브 단계
                // j단계 드래곤 커브 시작
                lastPos = makeDragonCurve(lastPos[0], lastPos[1], dirList.size());  // 드래곤 커브 함수 호출
                //printDragonCurve();
                //System.out.printf("%d단계 완료\n\n", j + 1);
            }
        }
        System.out.println(countDragonCurve());  // 사각형 개수 세기
    }

    private static int[] makeDragonCurve(int r, int c, int count) {
        if (count == 0) return new int[]{r, c};  // 드래곤 커브 끝점 반환

        int nd = (dirList.get(count - 1) + 1) % 4;  // 드래곤 커브 진행 방향 계산
        int nr = r + dr[nd];
        int nc = c + dc[nd];

        dirList.add(nd);  // 진행 방향을 방향 List에 삽입
        dragonCurve[nr][nc] = true;  // 방문 체크
        //System.out.printf("%3d: (%d, %d)에서 (%d, %d)로 이동\n", count, r, c, nr, nc);
        return makeDragonCurve(nr, nc, count - 1);  // 이전 드래곤 커브에 따른 다음 드래곤 커브 선 그리기
    }

    private static int countDragonCurve() {
        int count = 0;
        for (int i = 1; i <= 100; i++) {
            for (int j = 1; j <= 100; j++) {
                // 방문한 점으로 사각형을 만들 수 있을 경우
                if (dragonCurve[i][j] && dragonCurve[i - 1][j] && dragonCurve[i][j - 1] && dragonCurve[i - 1][j - 1]) {
                    count++;  // count + 1
                }
            }
        }

        return count;
    }

    private static void printDragonCurve() {
        for (int i = 1; i <= 5; i++) {
            for (int j = 1; j <= 5; j++) {
                System.out.printf("%1s ", dragonCurve[i][j] ? "T" : "F");
            }
            System.out.println();
        }
        System.out.println("=====================");
    }
}

 

처음엔 방향 자체를 dragonCurve 이차원 배열에 int 형식으로 저장하여, 방향 존재 여부로 방문 여부를 판단했다.

하지만 이전에 만든 드래곤커브를 찾으며 요소가 겹칠 수 있다는 것을 구현한 후에 깨달아서...

4번째 테스트 케이스에서 48이 나오는 분들은 나와 같은 실수를 하지 않았나 확인해 보길 바란다 ㅠㅠ.

 

단순한 구현 문제로, 90도 회전하는 방향을 찾아가는 것에 대한 이해 + 문제 자체의 이해 능력이 중요한 문제였다.

나는 처음에 입력 란에서 'x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대'라는 말이 있어,

(y, x)가 g 세대의 시작점이라고 잘못 이해하고 엄청나게 좌표 손그림을 그렸다... 

(y, x)는 최초 0세대 드래곤 커브의 시작점이다. 나와 같이 착각하는 일이 없도록 ㅠㅠ

 

문제의 구현 자체보단, 착각의 착각의 착각에 의해 시간이 오래 걸린 문제였다.