15683. 감시

dir을 이용해서 방향을 체크하였다.  

시간복잡도가 최악의 경우라고 하더라도 4의 8승 * 8의 2승 = 2의 24승 정도로 계산되어서 모든 경우를 백트래킹으로 살펴보았다.

 

처음에 방향을 이상하게 잡아서 삽질을 엄청 많이한 문제였다..  

자바를 이용한 알고리즘 문제풀이를 별로 안해봐서 그런지 코드도 엄청 길어졌다. ㅠ

 

 

 

 

 

 

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

public class Main {
    public static int ans, N, x, y, d, g;
    public static boolean[][] MAP = new boolean[101][101];

    public static void InputData() {
        try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
            N = Integer.parseInt(stk.nextToken());

            while(N > 0){
                stk = new StringTokenizer(br.readLine(), " ");
                x = Integer.parseInt(stk.nextToken());
                y = Integer.parseInt(stk.nextToken());
                d = Integer.parseInt(stk.nextToken());
                g = Integer.parseInt(stk.nextToken());

                Dragoncurve(x,y,d,g);

                N--;
            }

            ans = 0;
            for(int i = 0; i < 100; i++){
                for(int j = 0; j < 100; j++){
                    if(MAP[i][j] && MAP[i+1][j] && MAP[i][j+1] && MAP[i+1][j+1]){
                        ans++;
                    }
                }
            }// N^2

        }catch (IOException e){
            e.printStackTrace();
        }
    } // 데이터 입력

    public static void Print_result(){
        try(BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))){
            bw.write(String.valueOf(ans));
            bw.flush();
        } catch (IOException e) {
            e.printStackTrace();
        }
    } // 결과 출력

    private static void Dragoncurve(int x, int y, int d, int g) {
        Stack<Pos> posStack = new Stack<>();
        posStack.push(new Pos(x,y));
        switch(d){
            case 0:
                posStack.push(new Pos(x+1,y));
                MAP[x][y] = MAP[x+1][y] = true;
                break;
            case 1:
                posStack.push(new Pos(x,y-1));
                MAP[x][y] = MAP[x][y-1] = true;
                break;
            case 2:
                posStack.push(new Pos(x-1,y));
                MAP[x][y] = MAP[x-1][y] = true;
                break;
            default:
                posStack.push(new Pos(x,y+1));
                MAP[x][y] = MAP[x][y+1] = true;
                break;
        }

        for(int i = 0; i < g; i++){
            Stack<Pos> Temp = (Stack<Pos>) posStack.clone();
            Pos prev = posStack.peek();
            while(!posStack.isEmpty()){
                Pos now = posStack.pop();

                int sub_x = prev.x - now.x;
                int sub_y = prev.y - now.y;

                if(sub_x > 0) {
                    Pos tail = Temp.peek();
                    Temp.push(new Pos(tail.x, tail.y - 1));
                }else if(sub_x < 0) {
                    Pos tail = Temp.peek();
                    Temp.push(new Pos(tail.x, tail.y + 1));
                }else if(sub_y > 0) {
                    Pos tail = Temp.peek();
                    Temp.push(new Pos(tail.x + 1, tail.y));
                }else if(sub_y < 0) {
                    Pos tail = Temp.peek();
                    Temp.push(new Pos(tail.x - 1, tail.y));
                }
                prev = now;
            }
            posStack = Temp;
        }
        while(!posStack.isEmpty()){
            Pos top = posStack.pop();
            MAP[top.x][top.y] = true;
        }
    }

    static class Pos{
        int x, y, dir;
        Pos(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args){
        InputData();
        Print_result();
    }
}