백준 15695 - 드래곤 커브

www.acmicpc.net/problem/15685

15685번: 드래곤 커브

시뮬레이션 문제는 조금 더 간단하게 규칙을 파악할 필요가 있는 것 같다.

 

 

import java.io.IOException;
import java.io.*;
import java.util.*;
 
 
public class B15685 {
    static int[] dy = {0 , -1, 0 , +1};
    static int[] dx = {+1, 0 , -1 , 0};
    static boolean[][] board = new boolean[101][101];
    public static class Point {
        int x;
        int y;
 
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public static void makeDragonCurve(Point start,int generation , ArrayList<Integer> route , int dir , int aimGen) {
        // for(int i=0 ; i<=10 ; i++) {
        //     for(int j=0 ; j<=10 ; j++) {
        //         System.out.print(board[i][j] +" ");             
        //     }
        //     System.out.println();
        // }
        // System.out.println();
        if(generation == aimGen) return;
        //0세대 , 1세대를 제외하고         
        else if(generation == 0) {
            route.add(dir);
            int nx = start.x + dx[dir];
            int ny = start.y + dy[dir];
            board[nx][ny] = true;
            makeDragonCurve(new Point(nx, ny), generation + 1, route, dir , aimGen);
        }else{              
            //0~2/len 까지는 -1곱한 값 , 2/len ~ len 까지는 기존 값으로 진행된다.
            int size = route.size();
            Point point = start;
            
            for(int i = size-1 ; i >= 0 ; i--){ 
                int tmp = route.get(i);
                int nextDir = (tmp + 1) % 4;
 
                route.add(nextDir);
                point.x += dx[nextDir];
                point.y += dy[nextDir];
                
                board[point.x][point.y] = true;    
            }
 
            makeDragonCurve(point, generation+1, route, dir, aimGen);
        }
 
    }
    public static int countSquare() {
        int count = 0;
        for(int i=0 ; i<100 ; i++) {
            for(int j=0 ; j < 100 ; j++) {
                if(board[i][j]&&board[i][j+1]&&board[i+1][j]&&board[i+1][j+1]) {
                    count++;
                }
            }
        }
        return count;
    }
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String[] inputs;
        for(int i = 0 ; i < N ; i++) {
            inputs = br.readLine().split(" ");
            int x = Integer.parseInt(inputs[0]);
            int y = Integer.parseInt(inputs[1]);
            int dir = Integer.parseInt(inputs[2]);
            int aimGen = Integer.parseInt(inputs[3]);
            ArrayList<Integer> list = new ArrayList<Integer>();
            board[x][y] = true;
            makeDragonCurve(new Point(x, y), 0,list , dir ,aimGen+1);
        }       
        System.out.println(countSquare()); 
    }    
}