[백준] 15685.드래곤 커브 (java) / 시뮬레이션

@시뮬레이션 / 2h 15m

핵심 로직은 바로 생각해 냈는데, x축 y축이 반대인데 여기서 헷갈려서

한시간 넘게 삽질했다...ㅎㅎ

 

 

문제 링크

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

15685번: 드래곤 커브

 

 

구현 포인트

드래곤 커브를 어떻게 그릴 것인가 가 문제의 핵심인데, 핵심만 잘 잡으면 간단하게 구현 할 수 있다.

 

문제 설명

 

잘 읽어 보면, 지금까지 만든 드래곤 커브를 회전시켜서, 지금 드래곤 커브의 끝 점에 붙인다는 뜻인데,

결국 동일한 드래곤커브 두개를 방향만 다르게 해서 끝점끼리 붙여준다는 뜻이다.

 

 

그래서 다음 세대의 드래곤커브를 만들 때에는,

지금 세대의 드래곤커브의 끝 점에

똑같은 드래곤커브를 뒤집어서 + 방향을 꺾어서 붙여주면 된다.

 

 

 

 

삽질 포인트

x축이 가로, y축이 세로 방향인데 이것때문에 엄청 헷갈렸다.

그냥 내가 기준을 잡아 놓고, 그 기준에 맞게 입력받고, 방향을 설정하면 된다.

나는 보통 (i, j) 좌표에서 i를 행, j를 열으로 두고 풀어서

익숙한 이 방식으로 쓰기 위해 3가지 설정을 했다.

 

 

1) 입력 : x축과 y축을 반대로 입력받았다.

 

2) 이동 방향 :

문제 설명에 따르면 0:우 / 1:상 / 2:좌 / 3:하 이다.

그래서 이렇게 방향을 설정했다.

 

 

3) 회전 방향

가장 헷갈렸던 부분은, 축을 바꾸면 회전시 방향이 어떻게 변하는가 였는데

문제에서 주어진 대로 끝점을 기준으로 90도씩 회전하면

→ 방향부터 시작했을 때, 우 하 좌 상 이 된다.

 

그림을 그려놓고 생각하면 좀 더 쉽다.

문제에서 주어진 축 기준

이걸 x축-y축을 바꿔서 생각하면 우 상 좌 하가 되는데,

마침 이 순서가 문제에서 주어진 순서여서 다음 방향을 찾을 때는 (현재 방향 + 1) % 4 만 해주면 쉽게 풀린다.

 

한시간동안 수십번은 바꿔 본 것 같다.

헷갈릴 때는 그림이 최고!

 

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	
	private static final int SIZE = 101;
	private static int N, count = 0;
	private static int[] dx = {0, -1, 0, 1}, dy = {1, 0, -1, 0};	//x, y 바꿔서 입력받음 / 우상좌하 순서 
	private static boolean[][] map;
	private static LinkedList<Integer> list;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		map = new boolean[SIZE][SIZE];
		N = Integer.parseInt(br.readLine());
		
		int x, y, d, g;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			y = Integer.parseInt(st.nextToken());	//x, y 바꿔서 입력받음 
			x = Integer.parseInt(st.nextToken());
			d = Integer.parseInt(st.nextToken());
			g = Integer.parseInt(st.nextToken());
			
			list = new LinkedList<Integer>();
			list.add(d);
			curveMake(g);
			drawCurveMap(x, y);
		}
		checkMap();
		System.out.println(count);
	}

	private static void checkMap() {
		for (int i = 0; i < SIZE - 1; i++)
			for (int j = 0; j < SIZE - 1; j++)
				if (map[i][j] && map[i][j + 1] && map[i + 1][j] && map[i + 1][j + 1])
					count++;
	}

	private static void drawCurveMap(int x, int y) {
		int nx = x, ny = y;
		int size = list.size();

		map[x][y] = true;
		
		for (int i = 0; i < size; i++) {
			int d = list.get(i);
			
			nx += dx[d]; ny += dy[d];
			map[nx][ny] = true;
		}
	}

	private static void curveMake(int curve) {
		for (int c = 0; c < curve; c++) {
			int size = list.size();
			//매번 지금 길이만큼을 더해주는데, 이때 1)뒤집어서, +1씩 인덱스를 더해서 list에 추가해준다. 
			for (int i = 1; i <= size; i++)
				list.add((list.get(size - i) + 1) % 4);
		}
	}
}

 

 

어려운 부분은 잘 풀어 놓고

정작 쉬운 부분에서 삽질했던 문제였다. 그래도 재미있는 문제였다.

 

끝!