[BOJ 15685] 드래곤 커브 (Java)

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

15685번: 드래곤 커브

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_BOJ_15685 {
	static int N;
	static boolean[][] map=new boolean[101][101];
	static int[] dy= {0,-1,0,1};
	static int[] dx= {1,0,-1,0};
	static int answer=0;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(br.readLine());
		int x, y, d, g;
		StringTokenizer st;
		for (int i=0; i<N; i++) {
			st=new StringTokenizer(br.readLine());
			x=Integer.parseInt(st.nextToken());
			y=Integer.parseInt(st.nextToken());
			d=Integer.parseInt(st.nextToken());
			g=Integer.parseInt(st.nextToken());
			map[y][x]=true;
			visit(y,x,d,g);
		}
		for (int r=0; r<100; r++) {
			for (int c=0; c<100; c++) {
				if (check(r,c)) answer++;
			}
		}
		System.out.println(answer);
	}
	
	private static boolean check(int r, int c) {
		for (int i=r; i<r+2; i++) {
			for (int j=c; j<c+2; j++) {
				if (!map[i][j]) return false;
			}
		}
		return true;
		
	}

	private static void visit(int y, int x, int d, int g) {
		List<DragonCurve> li=new ArrayList<>();
		int ny=y+dy[d];
		int nx=x+dx[d];
		int nd;
		li.add(new DragonCurve(ny, nx, d));
		if (isValid(ny, nx)) map[ny][nx]=true;
		for (int i=0; i<g; i++) {
			int last=li.size()-1;
			int prev_y=li.get(last).r;
			int prev_x=li.get(last).c;
			for (int j=last; j>=0; j--) {
				nd=(li.get(j).d+1)%4;
				ny=prev_y+dy[nd];
				nx=prev_x+dx[nd];
				li.add(new DragonCurve(ny,nx,nd));
				if (isValid(ny,nx)) map[ny][nx]=true;
				prev_y=ny;
				prev_x=nx;
			}
		}
	}
	
	private static boolean isValid(int y, int x) {
		return y>=0 && y<=100 && x>=0 && x<=100;
	}

	public static class DragonCurve{
		int r, c, d;
		private DragonCurve(int r, int c, int d) {
			this.r = r;
			this.c = c;
			this.d = d;
		}
	}
	

}

0방향=>시계방향 90도로 움직일 경우 1방향, 

1방향=>시계방향 90도로 움직일 경우 2방향.. 임을 발견하자.

그리고 직전 위치+이전에 나왔던 커브들의 directon들을 이용해 드래곤 커브들을 완성한다.

 

1. 드래곤 커브의 시작점 (y,x) 를 받고, 그 방향에 따라 움직인 끝점 ny, nx와 방향 d를 리스트에 담는다. ny,nx 가 영역에 있으면 map에 표시한다.

2. 다음과 같은 연산을 g번 반복한다.

 2-1. 한 세대를 시작할 때, 그 이전 세대의 가장 마지막 점을 리스트에서 가져온다.

 2-2. 이전 세대들의 드래곤 커브들을 제일 마지막부터 처음까지 접근하면서 방향 d를 가져와 (d+1)%4 해줘서 시계방향 90도 이동한 방향으로 바꿔준다. 직전 점 prev_y, prev_x에 각각 ny[d], nx[d] 를 더해줘서 회전된 드래곤 커브를 만든다. map에 표시한다. 더해준 값이 다음 드래곤 커브를 만드는데 필요하므로, prev_y, prev_x에 그 값을 저장한다.

 

이 문제의 포인트는" 이제까지 쌓아왔던 드래곤 커브들을 뒤에서부터 거꾸로 접근해 방향값을 가져오는 것 + 이전 드래곤 커브의 끝점을 이용해 현재 드래곤 커브를 만들어 주는 것" 이다.

 

다른 분들의 코드를 보니, DragonCurve 객체는 만들 필요 없이, arrayList에 이전 드래곤 커브들의 방향값만 저장해 주면 된다. 끝점의 위치는 end_y, end_x 변수를 이용해 계속 움직이면서 저장하도록 하면 더 코드가 간결해진다.

 

 

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_BOJ_15685_2 {
	static int N;
	static boolean[][] map=new boolean[101][101];
	static int[] dy= {0,-1,0,1};
	static int[] dx= {1,0,-1,0};
	static int answer=0;
	static int end_y, end_x;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(br.readLine());
		int x, y, d, g;
		StringTokenizer st;
		for (int i=0; i<N; i++) {
			st=new StringTokenizer(br.readLine());
			x=Integer.parseInt(st.nextToken());
			y=Integer.parseInt(st.nextToken());
			d=Integer.parseInt(st.nextToken());
			g=Integer.parseInt(st.nextToken());
			map[y][x]=true;
			end_y=y+dy[d];
			end_x=x+dx[d];
			map[end_y][end_x]=true;		//0세대 만들어놓기
			List<Integer> dirs=new ArrayList<>();
			dirs.add(d);
			for (int j=0; j<g; j++) {
				visit(dirs);
			}
		}
		for (int r=0; r<100; r++) {
			for (int c=0; c<100; c++) {
				if (check(r,c)) answer++;
			}
		}
		System.out.println(answer);
	}
	
	private static boolean check(int r, int c) {
		for (int i=r; i<r+2; i++) {
			for (int j=c; j<c+2; j++) {
				if (!map[i][j]) return false;
			}
		}
		return true;
		
	}

	private static void visit(List<Integer> dirs) {
		int len=dirs.size()-1;
		for (int i=len; i>=0; i--) {
			int d=(dirs.get(i)+1)%4;
			end_y=end_y+dy[d];
			end_x=end_x+dx[d];
			dirs.add(d);
			map[end_y][end_x]=true;
		}
	}
}

다시 짠 코드..