/ BOJ

BOJ_15685_드래곤커브_JAVA

문제 : 드래곤커브

링크 : BOJ_15685_드래곤커브

접근 방식

선분을 시계방향으로 90도 회전시킨다는 의미가 이해가 안됐고, 끝점을 기준으로 이어붙인다는 것에 대한 의미도 잘 모르겠어서 상당히 난항을 겪었던 문제다.

고민을 오래 했지만 의외로 문제가 쉽게 풀렸는데, 0세대 드래곤 커브부터 4세대 드래곤 커브까지 그려놓고 보니 규칙이 보였다.

15685_1

그림을 보면 0~4세대의 드래곤 커브를 그려보았다. 그리고, 각각의 방향을 구하여 나열해보았다.

0 01 0121 01212321 0121232123432321

언뜻 보면 규칙이 없는 것처럼 보이지만, N-1항을 기준으로 N항을 살펴보면 규칙을 찾을 수 있다.

규칙 : N번째 드래곤 커브는 N-1번째 드래곤 커브 + N-1번째 드래곤 커브의 역순의 수에 각각 +1씩 더해준 값이 된다.

말로 설명하면 이와 같은 규칙이 된다. 예시를 들어보자.

위 예제에서 2세대 드래곤 커브는 0121이다.

2세대 드래곤커브는 0121, 여기에 1씩 더한 후 거꾸로 나열하면 2321이다.

2세대 드래곤커브에 거꾸로 나열한 수를 합치면 01212321이 된다.

이 수열이 3세대 드래곤 커브가 되는 것이다.

이렇게 0세대부터 10세대까지 모든 드래곤 커브를 구한 뒤에, 시작점부터 구한 드래곤 커브의 방향 순서대로 드래곤 커브를 그리면 된다.

그렇게 모든 드래곤 커브를 구한 뒤에, 1*1크기의 정사각형을 탐색하여 모두 그려진 상태라면 카운트를 1씩 늘려주고, 탐색이 모두 완료되면 카운트한 값을 출력해주면 된다.

소스 코드

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

public class BOJ_15685_드래곤커브 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int[][] dir = { { 0, 1 }, { -1, 0 }, { 0, -1 }, { 1, 0 } };

		int N = Integer.parseInt(in.readLine());

		// 0
		// 01
		// 0121
		// 01212321
		// 0121232123432321
		// 거꾸로 가면서 1씩 더하기
		int[][] map = new int[101][101];
		int answer = 0;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine(), " ");

			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			int g = Integer.parseInt(st.nextToken());

			List<Integer> dp[] = new ArrayList[11];

			for (int j = 0; j <= 10; j++) {
				dp[j] = new ArrayList<>();
			}

			dp[0].add(d);

			for (int j = 1; j <= 10; j++) {
				List<Integer> temp = new ArrayList<>();
				for (int k = dp[j - 1].size(); k > 0; k--) {
					temp.add(dp[j - 1].get(k - 1) + 1);
				}
				// 0121 - j-1
				// 2321 - temp
				for (int k = 0, n = dp[j - 1].size(); k < n; k++) {

					dp[j].add(dp[j - 1].get(k));
					// 0121 - j
				}

				for (int k = 0, n = temp.size(); k < n; k++) {
					dp[j].add(temp.get(k));
				}
				// 01212321 - j
			}

			map[y][x] = 1;

			for (int j = 0, n = dp[g].size(); j < n; j++) {

				int dx = x + dir[dp[g].get(j) % 4][1];
				int dy = y + dir[dp[g].get(j) % 4][0];

				map[dy][dx] = 1;

				x = dx;
				y = dy;
			}

		}

		for(int j=0;j<100;j++) {
			for(int k=0;k<100;k++) {
				if(map[j][k] == 1 && map[j+1][k] == 1 && map[j][k+1] ==1 && map[j+1][k+1] == 1) {
					answer++;
				}
			}
		}
		System.out.println(answer);

	}

}

좌표정보와 시계방향 회전에 매여서 시간이 오래걸린 문제였지만, 관점을 다르게 하고보니 쉽게 풀렸다. 운이 좋았다고 할 수 있다.