[백준] 15685 드래곤 커브

문제 출처: www.acmicpc.net/problem/15685

15685번: 드래곤 커브

: 먼저 각각의 주어진 좌표와 시작 방향, 드래곤 커브의 세대를 바탕으로 어떠한 방향이 이어지는지를 구해야 한다.

: 규칙을 찾아보면 다음과 같다.

오른쪽 방향 : 0 / 위쪽 방향 : 1 / 왼쪽 방향 : 2 / 아래쪽 방향 : 3 으로 둔다.

 

(0세대부터 누적했을 경우)

0세대 드래곤 커브 : 0

1세대 드래곤 커브 : 0 / 1

2세대 드래곤 커브 : 0 / 1 / 2 1

3세대 드래곤 커브 : 0 / 1 / 2 1 / 2 3 2 1

 

규칙을 찾아 보면 그 전 세대의 흐름을 거꾸로 하여 1씩 키워나가고 있음을 알 수 있다.

예를 들어 전 세대의 흐름이 1 2 3이라면 이를 거꾸로 하면 3 2 1이 되고 1씩 키우면 4 3 2가 되는데, 이때 방향은 0, 1, 2, 3만 존재하기 때문에 모듈러 연산을 4로 해준다.

그러면 4 3 2 는 0 3 2가 된다.

따라서 3세대의 마지막 커브를 보면 그 전 흐름인 0 1 2 1을 거꾸로 해서 1 2 1 0이 되고 여기에 1씩 더하면 2 3 2 1이 됨을 알 수 있다.

 

이러한 방법을 통해 각 줄의 정보로 드래곤 커브 움직임을 얻을 수 있고, 이를 지도에 표시 한다.

주의할 점은 x, y가 행렬이 아니라 좌표처럼 주어진다는 것이다.

 

지도에 모두 표시한 후 지도를 완전탐색하며 4개의 꼭짓점이 모두 드래곤 커브를 지나는지를 판단해주면된다.

출력을 보면 1x1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부의 것의 개수를 출력하라고 되어있다.

 

다음과 같은 방식으로 4개가 존재함을 알 수 있다. 변에 집중하지 않고 꼭짓점의 개수가 4개를 만족하는지에 집중해야 한다.

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 드래곤커브 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int N;
	static int[] dr = {0, -1, 0, 1};
	static int[] dc = {1, 0, -1, 0};
	public static void main(String[] args) throws NumberFormatException, IOException {
		N = Integer.parseInt(br.readLine());
		boolean[][] map = new boolean[101][101];
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			int g = Integer.parseInt(st.nextToken());
			List<Integer> movement = getMovement(g, d);
			// 움직임 표시
			int nr = x;
			int nc = y;
			map[nr][nc] = true;
			for(int m = 0, size = movement.size(); m < size; m++ ) {
				int cur = movement.get(m);
				nr += dr[cur];
				nc += dc[cur];
				map[nr][nc] = true;
			}
		}
		int res = calc(map);
		System.out.println(res);
	}
	private static int calc(boolean[][] map) {
		int cnt = 0;
		for(int i = 0; i < 100; i++) {
			for(int j = 0; j < 100; j++) {
				if(map[i][j] && map[i+1][j] && map[i][j+1] && map[i+1][j+1]) cnt++;
			}
		}
		return cnt;
	}
	public static List<Integer> getMovement(int g, int d) {
		List<Integer> move = new ArrayList<>();
		move.add(d);
		while(g-->0) {
			for(int i = move.size()-1; i >= 0; i-- ) {
				int dir = (move.get(i)+1)%4;
				move.add(dir);
			}
		}
		
		return move;
	}
}