백준 - 드래곤 커브 (15685)

1. 문제

문제 링크

2. 풀이

이 문제는 커브가 생성되는 규칙을 찾아내는 문제입니다.
단순히 머릿속에서 생각하지말고 직접 종이에 써가며 규칙을 찾는 방법이 제일 빠릅니다.

각설하고, 문제에서 제시한 예시를 기반으로 제가 찾은 규칙은 이렇습니다.

세대	진행 방향
0	→
1	→ ↑
2	→ ↑ ← ↑
3	→ ↑ ← ↑ ← ↓ ← ↑

이전 세대를 뒤에서부터 반시계 방향으로 회전시킨 방향을
다음 세대로 추가합니다.

예를 들면
1세대의 → ↑은 뒤에서부터 반시계 방향으로 회전시키면 ← ↑이 되고
2세대는 → ↑ ← ↑가 됩니다.

규칙을 알았으니 계획을 세워봅시다.

1. 커브 방향을 리스트에 넣고 진화 세대만큼 뒤에서부터 반시계 방향으로 회전시켜 새로 추가합니다.
2. 진화를 마쳤으면 테이블에 드래곤 커브를 그립니다.
3. 정사각형의 개수를 구합니다.

3. 전체 코드

import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	public static void main(String[] args) throws Exception {
		final int SIZE = 101;
		int[] my = {0, -1, 0, 1};
		int[] mx = {1, 0, -1, 0};
		
		boolean[][] M = new boolean[SIZE][SIZE];
		List<Integer> dirs = new ArrayList<>();
		
		int N = Integer.parseInt(br.readLine());
		
		for (int i = 0; i < N; i++) {
			StringTokenizer stk = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(stk.nextToken());
			int x = Integer.parseInt(stk.nextToken());
			int d = Integer.parseInt(stk.nextToken());
			int g = Integer.parseInt(stk.nextToken());
			
			// 1. 커브 방향을 리스트에 넣고 진화 세대만큼 뒤에서부터 반시계 방향으로 회전시켜 새로 추가합니다.
			dirs.add(d);
			
			for (int j = 0; j < g; j++) {
				for (int k = dirs.size() - 1; k >= 0; k--) {
					dirs.add((dirs.get(k) + 1) % 4);
				}
			}
			
			// 2. 진화를 마쳤으면 테이블에 드래곤 커브를 그립니다.
			M[y][x] = true;
			
			for (int dir: dirs) {
				y += my[dir];
				x += mx[dir];
				M[y][x] = true;
			}
			
			dirs.clear();
		}
		
		// 3. 정사각형의 개수를 구합니다.
		int ans = 0;
		
		for (int i = 0; i < SIZE - 1; i++) {
			for (int j = 0; j < SIZE - 1; j++) {
				if (M[i][j] && M[i][j + 1] && M[i + 1][j] && M[i + 1][j + 1]) {
					ans++;
				}
			}
		}
		
		bw.write(ans + "");
		bw.close();
	}
}