15685. 드래곤 커브

 

 

 

맨 끝점을 기준으로 전체 좌표를 시계방향으로 이동시키는 문제였다.  

맨 끝점을 시작으로 역순으로 좌표탐색을 하면서 풀 생각을 했기때문에 스택 자료구조를 사용하였다. 

 

스택에서 끝점 하나를 빼놓고 `prev`로 두고, 그 이후부터 빼는 점을 `now`로 뒀다. 

 

prev - now 의 결과 좌표를 가지고 4가지를 체크하였다.

 

1. x좌표가 음수 : 가장 최근에 입력된 점 기준으로 `y + 1`한 좌표가 다음 좌표

2. x좌표가 양수 : 가장 최근에 입력된 점 기준으로 `y - 1`한 좌표가 다음 좌표

3. y좌표가 음수 : 가장 최근에 입력된 점 기준으로 `x + 1`한 좌표가 다음 좌표

4. y좌표가 양수 : 가장 최근에 입력된 점 기준으로 `x - 1`한 좌표가 다음 좌표

 

이렇게 4가지를 기준으로 좌표값을 계속해서 스택에 저장한다음, 전체 스택을 가지고 답을 출력했다.

 

 

 

 

 

 

 

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();
    }
}