[PS] 백준 15685 : 드래곤 커브

※ https://rh-tn.tistory.com/ 와 동시에 업로드 됩니다.

문제

https://www.acmicpc.net/problem/15685

15685번: 드래곤 커브

 

해설

단순 구현 시뮬레이션 문제이지만 패턴을 발견하기 까지 고민을 좀 요구했던 문제이다. 

 

문제는 크게 두 부분으로 나눌 수 있다. 

 

1. 주어진 입력정보인 좌표(x, y), 시작 방향(d), 세대(g)를 입력받아 드래곤 커브 그리기

 

2. 네 꼭지점이 모두 드래곤 커브의 일부인 크기 1x1 정사각형을 몇개 만들 수 있는지 구하기

 

 

이 문제의 포인트는 바로 주어진 정보를 가지고 드래곤 커브를 그리는 것이다.

 

입력받은 정보를 바탕으로 다음 세대 드래곤 커브는 이전 세대 드래곤 커브를 시계방향으로 90도 회전하여 이전 세대 드래곤 커브의 끝점에 붙여서 그려지는데 

 

이 때 주어진 정보를 바탕으로 드래곤 커브를 그리게 되면, 끝점과 이동방향이 따로 놀아서 복잡하다.

 

몇번 그리다 보면 규칙을 찾을 수 있는 단서를 발견하게 되는데, 시계방향으로 회전한 이전 세대 드래곤 커브의 방향을 역방향으로 바꾸어 이전세대 끝에 붙이면 진행방향이 매끄러운 드래곤 커브가 그려진다는 것이다. 

 

이 때 방향이 추가되는 순서는 드래곤 커브에 추가된 이동방향의 역순이므로 이를 고려하여 드래곤 커브 이동방향에 대한 정보를 가지고 있으면 된다.

 

그렇게 구해진 드래곤 커브의 이동방향은 다음과 같은 패턴을 가진다. 

1. 이전 드래곤 커브에 추가된 누적된 이동 방향의 역순으로 다음 세대의 이동방향을 추가한다.

 

2. 이 때 한가지 패턴을 발견할 수 있는데 추가되는 방향은 현재 탐색중인 방향 바로 다음 방향을 가리킨다.

 

말로 설명하면 이해가 잘 안되는데 코드를 통해 직접 구현해보자

 

구현

import java.util.*;

public class Main {
	static StringBuilder sb = new StringBuilder();
	// 드래곤 커브의 개수 n
	static int n;
	// 좌표 x, y 방향 d 세대 g
	static int x, y, d, g;
	// 우 상 좌 하
	static int[] dy = {0, -1, 0, 1};
	static int[] dx = {1, 0, -1, 0};
	static int[][] map = new int[101][101];
	// 시작점으로 부터 커프를 만든다
	static void makeCurve(int x, int y, int dir, int gen) {
		// 이동 방향을 정할 List 생성
		ArrayList<Integer> list = new ArrayList<>();
		list.add(dir);
		// 이 때 이동방향은 추가된 순서의 역순으로 자기 다음 방향을 나타낸다.
		for(int i = 0; i<gen; i++) {
			int size = list.size();
			for(int j = size - 1; j>=0; j--) {
				list.add((list.get(j) + 1) % 4);
			}
		}
		// 시작 점을 1로 표시한다.
		map[y][x] = 1;
		// 시작점으로 부터 저장된 이동방향으로 나아가면서 지나가는 점들을 1로 표시한다.
		int nx = x, ny = y;
		for(int i = 0; i<list.size(); i++) {
			int dr = list.get(i);
			ny += dy[dr];
			nx += dx[dr];
			// 이미 지나온 길이므로 pass 한다.
			if(map[ny][nx] == 1) continue;
			map[ny][nx] = 1;
		}
	}
	// 해당 좌표에서 1 x 1 짜리 정사각형, 좌표상으로는 2 x 2 크기의 정사각형을 만들 수 있는지 체크
	static boolean check(int x, int y) {
		for(int i = x; i < x + 2; i++) {
			for(int j = y; j < y + 2; j++) {
				// 만들 수 없는 경우
				if(map[i][j] == 0) return false;
			}
		}
		return true;
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n = Integer.parseInt(br.readLine());
		for(int i = 0; i<n; i++) {
			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());
			// 입력받은 정보로 부터 드래곤 커브를 지도에 그린다.
			makeCurve(x, y, d, g);
		}
		int total = 0;
		for(int i = 0; i<100; i++) {
			for(int j = 0; j<100; j++) {
				// 각 좌표에서 정사각형을 그릴 수 있는 경우 개수를 추가한다.
				if(map[i][j] == 1) {
					if(check(i, j))
						total++;
				}
			}
		}
		System.out.println(total);
	}
}