[백준] 15685 - 드래곤 커브

[문제링크]

15685번: 드래곤 커브

 

0. N세대 드래곤 커브란? N-1세대 드래곤 커브를 끝 점 기준 90도 회전시켜 N-1세대의 끝 점에 붙인 것

  - 한 세대마다 2배씩 증가하지만, 세대가 최대 10이므로 최대 pow(2,10), 1024개의 지점으로 구성된다

 

1. N세대 드래곤 커브를 만들기 위해선?

  - N-1세대의 끝 점에서 시작해, N-1세대 커브의 구성을 역순으로 90도 회전시켜서 적용한다

2세대 커브

  - 예를들어, 위 2세대 커브는 →↑←↑ 순서로 이루어져 0, -2 지점에서 종료되었다.

  - 3세대 커브를 만들려면 0, -2 지점에서 2세대 커브의 역순인 ↑←↑→ 이동을, 90도 회전시켜 ←↓←↑ 순서로 진행하면 된다

3세대 드래곤 커브

  - 이는 문제 예시를 통해 확인 가능하다

 

2. 해당 과정을 위해 N세대까지 거쳐온 기록을 Arraylist로 저장하고, 이를 역순으로 탐색하며 끝점을 이동시킨다

 

3. 끝점은 분명한 경로를 가지고 움직이지만, 문제의 요구사항은 0<=x,y<=100 인 (x,y) 좌표에 대해서 정사각형을 구하는 것이므로, 끝 점이 방문한 좌표만 기록한다

 

4. 모든 커브가 그려진 후, 0~100의 좌표들에 대해서 사각형 조건 충족 여부를 검사, 출력한다

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

public class Main{
	
	static int[][] dir= {
			{0,1},
			{-1,0},
			{0,-1},
			{1,0}
	};
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int cntSquare=0;
		boolean[][] map = new boolean[101][101];
		
		int N = pint(br.readLine());
		for (int i = 0; i < N; i++) {

			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int y = pint(st.nextToken());
			int x = pint(st.nextToken());
			int d = pint(st.nextToken());
			int g = pint(st.nextToken());
			
			if(inBox(x,y)) {
				map[x][y]=true;
			}
			x+=dir[d][0];
			y+=dir[d][1];
			if(inBox(x,y)) {
				map[x][y]=true;
			}
			//curve의 경로 저장
			List<Integer>curve = new ArrayList<>();
			curve.add(d);
			
			for (int j = 0; j < g; j++) {
				for (int j2 = curve.size()-1; j2 >= 0; j2--) {
					//curve를 역순으로 탐색
					int curDir = curve.get(j2);
					//90도 회전
					int nextDir=(curDir+1)%4;
					//끝 점 이동 적용
					x+=dir[nextDir][0];
					y+=dir[nextDir][1];
					if(inBox(x,y)) {
						map[x][y]=true;
					}
					curve.add(nextDir);
				}
			}
			
		}
		
		//조건을 만족하는 사각형의 갯수 찾기
		for (int i = 0; i <100; i++) {
			for (int j = 0; j < 100; j++) {
				if(map[i][j] && map[i][j+1] && map[i+1][j] && map[i+1][j+1]) {
					cntSquare++;
				}
			}
		}
		System.out.println(cntSquare);
	}
	
	static boolean inBox(int x, int y) {
		if(x>=0 && x<=100 && y>=0 && y<=100)return true;
		return false;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

결과 화면