[JAVA/백준15685] 드래곤 커브

문제

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.

1. 시작 점
2. 시작 방향
3. 세대

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인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.

 

풀이

처음 시뮬레이션 문제를 풀었는데 규칙을 찾고 어떻게 접근해야하는지에 대해 시간이 오래 걸렸고, 힌트를 얻기 위해서 여러 블로그를 많이 참고하였다. 푸는 방법이 다양했지만 나는 스택을 공부한 상황이였기 때문에 스택을 활용하여 문제를 해결하였다.
문제와 같이 시작점이 (0,0)이고 시작방향이 →, 3세대까지 구한다고 가정하였을 때 각 세대별 끝점과 방향을 순서대로 나열하면 다음과 같다.

0세대 → (0,0)
1세대 → ↑ (1,-1)
2세대 → ↑ ← ↑(0,1)
3세대 → ↑ ← ↑←↓←↑ (0,1)

여기서, 규칙을 찾기 좋게 방향을 숫자 0(→),1(↑),2(←),3(↓)로 표현하면 다음과 같다.

0세대 0 
1세대 0 1
2세대 0 1 2 1
3세대 0 1 2 1 2 3 2 1 

방향을 보면 이전 세대에 대해 거꾸로 추적하면서 +1해서 이동하는 것을 알 수 있다.
3에서 1을 더하는 경우 다시 0이 되기 때문에, 규칙에 대한 점화식을 세우면 arrow = (arrow+1)%4가 됨을 알 수 있다.
따라서 이전 세대의 이동 방향을 순서대로 스택에 넣어주고, 다음 세대에서는 넣어둔 이전 세대의 방향을 하나씩 꺼내주고 (arrow+1)%4하여 다음 방향을 읽는다. 그리고 이 다음 세대에서도 추적할 수 있도록 스택에 넣어주도록 한다.

입력받는 드래곤 커브는 모두 같은 이차원 좌표 평면을 공유하므로 클래스변수 map[][]로 선언하고, 방향에 따라 끝점이 업데이트 될 때 마다 방문했음을 표시해주기 위해 map[][]변수에 해당 좌표에 true값을 넣는다. 
여기서 주의할 점은 방향에 따라서 좌표가 움직이는데 예를 들어 좌표가 (4,2)인 경우 방향이 1(↑)일 때 y좌표가 감소하여 (4,1)이 된다. 하지만 2차원 좌표를 그려보면 다음 그림 처럼 행:x좌표, 열:y좌표인 경우 그림이 다르게 그려진다.

이 문제에서는 드래곤커브들이 만드는 정사각형을 구하는것이 목적이기 때문에 그림이 같아야한다. 드래곤커브 그림과 2차원배열 에서의 그림이 같아지려면 행:y좌표, x:좌표를 표시해야 같아지는 것을 알 수 있다. 이 부분이 자꾸 헷갈려서 여러번 그리고 나서야 깨닫게 되었다.

모든 드래곤커브를 그리는 과정이 끝나면, 마지막에서는 map[][]에 있는 좌표 중에서 드래곤커브에 포함된 좌표들을 찾아서 해당 좌표들이 정사각형을 찾는지 구한다. 한 좌표(i,j)를 기준으로 오른쪽, 아래, 대각선 오른쪽 아래방향의 좌표가 모두 true이면 정사각형임을 알 수 있다. 

마지막으로 주의할 점은 문제에서 '입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다'고 명시되어 있으므로 격자 밖에 넘어가지 않는 좌표를 알맞게 입력해주어야 한다. 처음에는 이를 무시하고 문제에 있는 시작점 (0,0)과 방향:0, 세대:3으로 입력을 하니 오류가 떠서 코드가 잘못된 줄 알고 몇번이나 반복해서 다시 썻다 지웠다를 반복했는데 결국 문제를 제대로 읽지 않은 것이 원인이었다ㅜㅜ 

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

	public static int n; // 드래곤 커브의 개수
	public static int x, y, d, g; // x,y=시작점, d=시작방향, g=세대
	public static boolean[][] map = new boolean[101][101]; 
	public static int[] dx = { 1, 0, -1, 0 }; // 방향; →, ↑, ←, ↓
	public static int[] dy = { 0, -1, 0, 1 };
	public static Stack<Integer> stack; // 방향정보 저장 스택
	public static int end_x = 0;
	public static int end_y = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		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());
			d = Integer.parseInt(st.nextToken());
			g = Integer.parseInt(st.nextToken());

			// 스택 초기화
			stack = new Stack<Integer>();

			map[y][x] = true; // 시작점 지도에 표시

			// 0세대인 경우(스택에 아직 아무것도 저장 안되어있으므로 따로 빼준거)
			end_x = x + dx[d]; // 끝점
			end_y = y + dy[d];
			map[end_y][end_x] = true; // 0세대를 만든 후 지도에 표시한다.

			// 0세대의 방향 정볼르 스택에 넣음
			stack.push(d);

			// 1세대부터 g세대까지 다음 방향을 조사하면서 드래곤 커브 생성
			for (int j = 0; j < g; j++) {
				nextArrow();
			}
		}
		System.out.println(getSquare());
	}

	// 스택에 방향정보 저장하면서 드래곤 커스 생성
	public static void nextArrow() {
		int size = stack.size();
		for (int i = size - 1; i >= 0; i--) { // 스택에 담긴 방향 개수만큼 이동
			int next = (stack.elementAt(i) + 1) % 4;
			// 끝점 세팅
			end_x = end_x + dx[next];
			end_y = end_y + dy[next];
			// 방문했음을 지도에 표시, 2차원 배열에서는 행에 y, 열에 x를 넣어주어야 경로가 완성됨(그려보기)
			map[end_y][end_x] = true;
			stack.push(next);
		}
	}

	// 정사각형 구하기
	public static int getSquare() {
		int result = 0; // 정사각형의 개수
		for (int i = 0; i < 100; i++) {
			for (int j = 0; j < 100; j++) {
				// 인접한 4칸의 정사각형이 드래곤의 일부이면
				if (map[i][j] == true && map[i][j + 1] == true && map[i + 1][j] == true && map[i + 1][j + 1]) {
					result++;
				}
			}
		}
		return result;
	}
}

 

Reference

[백준] 15685 드래곤 커브