[BOJ]-15685 드래곤 커브

📌 문제 정보

• 문제 번호: BOJ 15685
• 문제 이름: 드래곤 커브
• 난이도: Gold
• 분류: 구현

---

🧩 문제 요약

• 주어지는 입력

n = 드래곤 커브의 개수
x = 시작 열 위치 
y = 시작 행 위치
d = 초기 방향
g = 세대 수

• 무엇을 구해야 하는지

드래곤 커브에 포함된 점들로 만들 수 있는 1X1의 정사각형 개수

---

💡 접근 아이디어

• 처음 떠올린 방법

처음 방법으로는 점들의 좌표를 반전 이동 시켜서 문제를 구현하려고 했다. 
그러나 방문한 점을 표현하는데 한계가 있었고 이를 해결하기 위해 
좌표를 반전시키는 것이 아닌 방향을 리스트에 담아 드래곤 커브를 구현하였다.

---

🛠️ 해결 전략

구현 흐름을 단계별로 정리합니다.

1. 상태 정의

좌표 이동을 담은 배열을 생성한다.
이때 순서는 반시계 방향을 참고했다.
끝점에서 시계 방향은 시작점에서 반시계 방향이다.

2. 핵심 로직(점화식 / 이동 규칙)

1. 가장 최근에 넣은 방향부터 1씩 더한 값을 방향 리스트에 넣어준다.

2. 방향 추가가 끝나면 이동 경로를 맵에 표시한다.

---

⚠️ 주의할 점

풀이 중 헷갈리거나 실수하기 쉬운 부분입니다.

드래곤 커브의 규칙성을 파악하는게 다소 어려웠다고 생각한다. 
해당 방법을 생각한 후에 나머지는 크게 어려운 부분이 없었다.

드래곤 커브 방향 리스트 예시

먼저 방향 기준을 다음과 같이 정의한다.

• 오른쪽 : 0
• 위쪽 : 1
• 왼쪽 : 2
• 아래쪽 : 3
  

---

✅ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	
	static int x, y;
	static int [][] moves = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
	static boolean [][] map = new boolean[102][102];
	
	public static void main(String [] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		for(int i=0;i<n;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			x = Integer.parseInt(st.nextToken());
			y = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			int g = Integer.parseInt(st.nextToken());
			
			map[y][x] = true;
			List<Integer> directions = new ArrayList();
			directions.add(d);
			for (int j=1;j<=g;j++) {
				spin90(directions);
			}
			
			for (int l = 0;l<directions.size();l++) {
				int dir = directions.get(l);
				move(dir);
			}
		}
		int ans = 0;
		for (int r=0;r<=100;r++) {
			for (int c=0;c<=100;c++) {
				// 이동한 좌표로 정사각형을 만들 수 있다면
				if (map[r][c] && map[r+1][c] && map[r][c+1] && map[r+1][c+1])
					ans++;
			}
		}
		
		System.out.println(ans);
	}
	
	static void move(int dir) {
		int ny = y + moves[dir][0];
		int nx = x + moves[dir][1];
		if (nx < 0 || nx > 100 || ny < 0 || ny > 100) 
			return ;
		map[ny][nx] = true;
		y = ny;
		x = nx;
	}
	
	static void spin90(List<Integer> li) {
		int size = li.size()-1;
		for (int i=size;i>=0;i--) {
			li.add((li.get(i) + 1) % 4);
		}
	}
}