백준 15685 드래곤 커브 자바(java)

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

15685번: 드래곤 커브

 

풀이 방법

구현, 시뮬레이션 문제이다.

드래곤 커브에서 다음 세대가 그려질 때 이동 방향을 알아야 좌표로 이동할 수 있다.

직접 그림을 그려보면 이동 방향의 규칙을 찾을 수 있다.

테스트 케이스 예제 1번의 2번째 예제를 가지고 살펴보았다.

 

 

0세대 : 1

1세대 : 1 2

2세대 : 1 2 3 2

3세대 : 1 2 3 2 3 0 3 2

 

세대 별 이동한 방향을 보면 이전 세대까지의 이동 방향을 뒤에서부터 차례대로 1씩 증가시킨 방향, 즉 반시계 방향으로 돌린 방향으로 이동한 것과 같다. 따라서 0세대의 방향부터 리스트에 삽입해놓고 다음 세대의 이동 방향을 구할 땐 리스트의 뒤에서부터 차례대로 접근하여 각 방향에 1씩 더한 방향을 삽입하여 저장한다.

위 방식으로 마지막 세대까지의 이동 방향을 모두 구했으면 리스트를 앞에서부터 순회하면서 방향에 따라 좌표를 이동하면서 좌표들을 방문 체크한다. 

 

코드

import java.io.*;
import java.util.*;

public class Main {

    static boolean[][] board = new boolean[101][101];
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, -1, 0, 1};

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

        int answer = 0;
        for(int i=0; i<100; i++) {
            for(int j=0; j<100; j++) {
                if(board[i][j] && board[i+1][j] && board[i][j+1] && board[i+1][j+1]){
                    answer++;
                }
            }
        }
        System.out.println(answer);
    }

    public static void dragonCurve(int x, int y, int d, int g) {
        List<Integer> dList = new ArrayList<>();
        dList.add(d);
        board[y][x] = true; // 0세대 시작점

        // g 세대까지 커브 반복
        for(int i=1; i<=g; i++) {
            for(int j=dList.size()-1; j>=0; j--) {
                dList.add((dList.get(j) + 1) % 4);
            }
        }
        for(Integer dir : dList) {
            // 다음 좌표로 이동
            x += dx[dir];
            y += dy[dir];
            board[y][x] = true;
        }
    }
}