알고리즘 - 드래곤 커브

문제

• 링크

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	static int[] dx = {1,0,-1,0};
	static int[] dy = {0,-1,0,1};
	static int N, answer;
	static boolean[][] arr = new boolean[101][101];
	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 stk = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(stk.nextToken()); 
			int y = Integer.parseInt(stk.nextToken());
			int d = Integer.parseInt(stk.nextToken());
			int g = Integer.parseInt(stk.nextToken());
			doTest(x,y,d,g);
			
		}
		
		for(int i = 0 ; i < 100 ; i++) {
			
			for(int j = 0 ; j < 100 ; j++) {
				
				if(arr[i][j] && arr[i][j+1] && arr[i+1][j] && arr[i+1][j+1] ) {
					answer++;
				}	
				
			}		
			
		}
		System.out.println(answer);
		
	}
	
	private static void doTest(int x, int y, int d, int g) {
		// TODO Auto-generated method stub

		Stack<Integer> pointList = new Stack<>();
		
		pointList.push(d);
		
		for(int i = 0; i < g ; i++) {			
			for(int j = pointList.size() - 1; j >= 0 ; j--) {
				pointList.push(((pointList.get(j)) + 1) % 4);
			}
		}
		
		arr[y][x] = true;
		
		for(Integer direct : pointList) {
			
			x += dx[direct];
			y += dy[direct];
			arr[y][x] = true;
			
		}
		
		
	}
}

회고

• 시뮬레이션 문제였음... 와.. 이걸 처음에 어떻게 풀어내야 할 지 고민을 많이 함

• 풀이를 참고해보니, 방향들을 하나씩 가져와 +1하면 반시계 방향으로 이동하는 것을 정의해두고 사용 하나씩 시작 지점 방향을 넣어 두고 방향들을 업데이트하며 점을 stack에 저장하며 점을 추가해 가며 업데이트

• arrayoutofindex : 0 <= x, y <= 100 범위를 가지고 있다는 것을 간과해서 오류가 발생했었음

• 참고 블로그! : 링크