드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.
시작 점 시작 방향 세대 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인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.
N // 드래곤 커브의 개수
x y d g // x좌표, y좌표, 시작 방향 d, 세대 g (N줄)
* 드래곤 커브 세대별 정의 0세대: 시작점 → 지정 방향 1칸 1세대: 0세대를 끝에서 90도 회전하여 이어붙임 2세대: 1세대를 끝에서 90도 회전하여 이어붙임 … g세대: 이전 세대의 방향들을 역순 + 회전하여 생성
* 규칙 구현 순서 1. 드래곤 커브의 방향을 세대별로 리스트에 저장 2. 시작 위치에서 각 방향을 따라 좌표 기록 3. 방문한 좌표를 boolean[101][101]에 표시 4. 최종적으로 1x1 정사각형이 형성된 칸 수를 세기
4) 코드
import java.util.*;
// Scanner, ArrayList 등 유틸리티 사용을 위해 import
public class Main {
static boolean[][] map = new boolean[101][101];
// 격자판 (0~100까지 사용) — 드래곤 커브가 지나간 점을 true로 표시
static int[] dx = {1, 0, -1, 0};
static int[] dy = {0, -1, 0, 1};
// 방향 배열 (0: 오른쪽, 1: 위쪽, 2: 왼쪽, 3: 아래쪽)
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 드래곤 커브의 개수
for (int t = 0; t < N; t++) {
int x = sc.nextInt(); // 시작 x좌표
int y = sc.nextInt(); // 시작 y좌표
int d = sc.nextInt(); // 시작 방향 (0~3)
int g = sc.nextInt(); // 세대 (0~10)
List<Integer> dirList = new ArrayList<>();
dirList.add(d); // 0세대: 시작 방향 하나만 존재
// g세대까지 방향 확장
for (int i = 0; i < g; i++) {
for (int j = dirList.size() - 1; j >= 0; j--) {
int nd = (dirList.get(j) + 1) % 4;
// 기존 방향을 역순으로 꺼내어 90도 회전한 방향 추가
dirList.add(nd);
}
}
// 시작 위치 방문 표시
map[y][x] = true;
// dirList에 따라 좌표를 이동하며 방문 표시
for (int dir : dirList) {
x += dx[dir];
y += dy[dir];
map[y][x] = true;
}
}
// 정사각형 개수 세기
int count = 0;
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
// (i,j) 기준으로 오른쪽, 아래, 오른쪽아래도 모두 true일 경우 정사각형
if (map[i][j] && map[i+1][j] && map[i][j+1] && map[i+1][j+1]) {
count++;
}
}
}
System.out.println(count); // 정답 출력
}
}
● 코드 작성 순서
단계
작성 대상
설명
1️⃣
dx[], dy[] 방향 배열
방향 계산의 핵심 도구로 가장 먼저 선언
2️⃣
map[101][101] 선언
방문 여부를 기록할 격자판 생성
3️⃣
main() 메서드의 입력 처리 부분
N, x, y, d, g 등 입력 받기 위한 뼈대 작성
4️⃣
List<Integer> dirList 생성
0세대 방향 저장 후 세대별 방향 확장 준비
5️⃣
세대 확장 로직 (for + reversed loop)
방향 리스트 확장 ((dir+1)%4) 구현
6️⃣
시작 위치 map[y][x] = true 표시
시작점 좌표 방문 처리
7️⃣
for-each dir → 커브 좌표 확장
방향 리스트를 따라 좌표 이동 및 방문 표시
8️⃣
격자 순회하여 정사각형 개수 세기
정답 계산을 위한 4칸 체크 로직 작성
9️⃣
System.out.println(count);
최종 결과 출력
5) 리뷰
기존 방향을 역순으로 돌려서 90도 회전한다는 공식을 이해하고 나니까 금방 구현할 수 있었습니다. 시뮬레이션 문제지만 방향 리스트가 핵심이었던 문제로, 시각화되게 머릿속으로 그려가며 구현하니 더 이해가 쉬운 문제였습니다.
