[백준 15685] 드래곤커브 - 자바(JVAVA)

1. 문제

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

15685번: 드래곤 커브

 

2. 풀이

핵심은 이 문장이라고 생각한다.

K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것

끝점을 기준으로 90도 회전했을 때 방향만 잘 구해주면 된다.

문제에 따르면 방향을 이렇게 설정했다.

• 0: x좌표가 증가하는 방향 (→)
• 1: y좌표가 감소하는 방향 (↑)
• 2: x좌표가 감소하는 방향 (←)
• 3: y좌표가 증가하는 방향 (↓)

끝 점을 기준으로 드래곤커브를 90도 시계 방향 회전할 때 방향이 0뱡향은 1, 1방향은 2, 2방향은 3, 3방향은 4, 4방향은 1이 되는 것을 그림을 그려보면 알 수 있다.

따라서 다음 방향을 찾을 때는 (현재방향+1)%4를 하면 구할 수 있다.

 

d_list에 방향값들을 먼저 저장하고 추후에 d_list로 시작 값부터 드래곤커브를 그렸다.

 

3. 소스코드

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

public class Main {
	static boolean[][] map=new boolean[101][101];
	static int[] dx= {1,0,-1,0}; //다음방향
	static int[] dy= {0,-1,0,1};
	static int cnt=0;
	
	public static void main(String[] args)throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int N=Integer.parseInt(br.readLine());
		for(int i=0;i<N;i++) {
			StringTokenizer st=new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());	//시작점x좌표
            int y = Integer.parseInt(st.nextToken());	//시작점y좌표
            int d = Integer.parseInt(st.nextToken());   // 시작 방향
            int g = Integer.parseInt(st.nextToken());   // 세대
            
            dragonCurve(x,y,d,g);
            
		}
		
		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++;
			}
		}
		System.out.println(cnt);
	}
	
	public static void dragonCurve(int x,int y,int d,int g) {
		List<Integer> d_list=new ArrayList<>(); //방향 담는 리스트
		
		d_list.add(d); //시작방향 넣기
		
		for(int i=1;i<=g;i++) {
			for(int j=d_list.size()-1;j>=0;j--) {
				int next_d=(d_list.get(j)+1)%4; //다음방향
				d_list.add(next_d);
			}
		}
		
		map[y][x]=true;
		for(Integer direction:d_list) {
			x+=dx[direction];
			y+=dy[direction];
			map[y][x]=true;
		}
	}
}