백준 15685 드래곤 커브 (Java)

1. 문제 링크

15685번: 드래곤 커브

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. 0세대 드래곤의 위치를 넣은 상태로 드래곤 커브를 시작한다.

2. 지금 위치에서 세대가 끝날 때까지 반복한다.

  2-1. 새로운 세대는 기존 세대에서 회전이 필요하기 때문에 회전이 시작되는 부분인 끝점부터 시작점까지 역순으로 넣는다.

  2-2. 끝점 기준 시계 방향은 지금 방향의 반시계이므로 주어진 방향과 동일하게 사용하기 때문에 +1한 값을 넣는다.

3. 모든 방향을 다 넣었다면 방문하면서 true로 바꾼다.

4. 완전 탐색을 통해 정사각형 전부 방문한 곳인지 확인하고 수를 센다.

 

4. 코드

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


public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] dx = {1, 0, -1, 0};
		int[] dy = {0, -1, 0, 1};
		boolean[][] map = new boolean[101][101];
		for(int i=0;i<N;i++) {
			String[] split = br.readLine().split(" ");
			int x = Integer.parseInt(split[0]);
			int y = Integer.parseInt(split[1]);
			int d = Integer.parseInt(split[2]);
			int g = Integer.parseInt(split[3]);

			ArrayList<Integer> dirlist = new ArrayList<>();
			dirlist.add(d);
			for(int j=0;j<g;j++) { //세대 만큼
				int size = dirlist.size();
				for(int k=size-1;k>=0;k--) { //회전해서 따라 만들어야 하니까 지금 끝점부터 옮기는 느낌으로
					dirlist.add((dirlist.get(k)+1) %4); //그려보니까 끝점 기준 시계 방향 => 지금 방향에서 반시계 방향 =>+1 하면 된다.
				}
			}
			
			map[x][y] = true;
			for(int dir: dirlist) {
				x+=dx[dir];
				y+=dy[dir];
				map[x][y] = true;
			}
		}
		
		int result = 0;
		for(int j=0;j<100;j++) {
			for(int k=0;k<100;k++) {
				if(map[j][k]&&map[j+1][k]&&map[j][k+1]&&map[j+1][k+1]) {
					result++;
				}
			}
		}
		System.out.println(result);	
	}
}