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

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

 

 

[ 문제 요약 ]

• 드래곤 커브는 이차원 좌표 평면 위에서 시작점, 시작 방향, 세대로 세 가지 속성으로 이루어집니다.
• 0세대 드래곤 커브는 길이가 1인 선분입니다. 0세대 드래곤 커브로 1세대 드래곤 커브를 만들 수 있습니다. 이때 방향이 모양을 좌우합니다.
• 방향이 오른쪽일 때, 1세대 드래곤 커브는 0세대 드래곤 커브의 끝 점(시작 점에서 가장 먼 점)을 기준으로 0세대 드래곤 커브의 모양을 시계 방향 90도 회전 시킨 다음 0세대 드래곤 커브의 끝 점에 붙입니다.
• K 세대 드래곤 커브는 K-1 세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향으로 회전 시킨 다음, 그것의 끝 점에 붙인 것입니다.
• 크기가 100 * 100인 격자 위에 드래곤 커브가 N 개가 있을 때, 1*1 크기의 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구합니다.
• 격자의 좌표는 (x, y)(x축은 → 방향, y축은↓)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표입니다.
• 입력에서 방향은 0, 1, 2, 3 중 하나이며 각 의미는 아래와 같습니다.
• 0: x좌표가 증가하는 방향 (→)
• 1: y좌표가 감소하는 방향 (↑)
• 2: x좌표가 감소하는 방향 (←)
• 3: y좌표가 증가하는 방향 (↓)

 

[ 테스트 케이스 설명 ]

4 // 드래곤 커브의 개수(1<=20)
3 3 0 1 // 드래곤 커브의 정보 x(시작점0<=100), y(시작점0<=100), d(시작 방향0<=3), g(세대0<=10)
4 2 1 3
4 2 2 1
2 7 3 4
네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형 개수 : 11

 

[ 알고리즘 분류 ]

• 구현
• 시뮬레이션

 

[ 문제 해설 ]

 

시작점과 끝점을 통해 지속적으로 좌표들을 구할 수 있습니다.

 

드래곤 커브에는 규칙이 있습니다. 시작점은 계속 똑같고, 끝점은, 시작점을 90도 회전시켰을 때 그 결과가 끝점으로 갱신됩니다.

[ 끝점 ]만 지속적으로 추적하면 좌표들의 리스트를 구할 수 있습니다.

 

끝점을 기준으로 모든 좌표를 90도 회전시켜 리스트로 관리합니다. 90도 회전 좌표를 구하는 것은 공식이 있어 구하기 쉽습니다.

 

(ny, nx) - (ey,ex) = (dy, dx)

gy = ey + dx

gx = ex - dy

 

위에서(ny, nx)는 구하려는 좌표이고, (ey, ex)는 끝점입니다. (dy, dx)는 두 좌표의 차이를 그대로 담은 것이고, gy와 gx는(ny, nx)를 90도 회전했을 때의 좌표가 됩니다. 즉 ny의 회전 y좌표는 끝점(ey)에 nx-ex를 더한 값이고, gx도 마찬가지로 공식으로 구합니다.

 

이렇게 90도 회전한 좌표를 구한 후 기존 좌표에 추가해서 리스트로 좌표를 관리해 줍니다.

 

그리고 꼭짓점이 사각형인지 확인하는 것은 boolean 2차원 배열에 마킹 해놓고, 4개의 사각형이 true 면 카운팅 하는 형식으로 간단히 구할 수 있습니다.

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
class Main{
	
	static final int len = 100;
	static List<Point> list;
	static boolean[][] map;
	static int sy, sx, ey, ex;
	static int d, g;
	static int N;
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());// 드래곤 커브의 개수(1<=20)
		list = new ArrayList<>();
		map = new boolean[len + 1][len + 1];
		
		while(N-->0)
		{
			st = new StringTokenizer(br.readLine());
			
			sx = Integer.parseInt(st.nextToken());// 드래곤 커브의 정보 x(시작점0<=100)
			sy = Integer.parseInt(st.nextToken());// y(시작점0<=100)
			d = Integer.parseInt(st.nextToken());// d(시작 방향0<=3)
			g = Integer.parseInt(st.nextToken());// g(세대0<=10)
			
			// 0세대 : 시작점과 방향으로 끝점을 구함
			ex = d == 0 ? sx + 1 : d == 2 ? sx - 1 : sx;
			ey = d == 1 ? sy - 1 : d == 3 ? sy + 1 : sy;
			
			list.clear();
			list.add(new Point(sy, sx));
			list.add(new Point(ey, ex));
			
			while(g-->0)
				rotateAppend();// 드래곤 커브를 list에 추가
			
			// 보드에 마킹
			for(Point n : list)
//				if(n.y>=0 && n.x>=0 && n.y<=len && n.x<=len) 문제 규칙상 범위를 벗어나지 않음
				map[n.y][n.x] = true;
		}
		System.out.print(print());
	}
	static void rotateAppend() {
		
		int size = list.size();
		
		for(int i=0; i<size; i++)
		{
			Point now = list.get(i);
			
			if(now.y == ey && now.x == ex)
				continue;
			
			Point next = getNext(now.y, now.x, ey, ex);
			list.add(next);
		}
		
		Point nextEnd = list.get(size);// size는 항상 첫번째 점의 90도를 회전한 것, 첫번째 점의 회전의 회전.. 이런식으로 나아감
		ey = nextEnd.y;
		ex = nextEnd.x;
	}
	static Point getNext(int ny, int nx, int ey, int ex) {
		/*
		공식
		(ny, nx) - (ey,ex) = (dy, dx)
		gy = ey + dx
		gx = ex - dy
		*/
		int dy = ny - ey;
		int dx = nx - ex;
		return new Point(ey + dx, ex - dy);
	}
	static int print() {
		int cnt = 0;
		
		for(int y=0; y<len; y++)
			for(int x=0; x<len; x++)
				if(map[y][x] && map[y+1][x] && map[y][x+1] && map[y+1][x+1])
					++cnt;
		
		return cnt;
	}
	static class Point{
		int y, x;
		Point(int y, int x){
			this.y=y;
			this.x=x;
		}
	}
}