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

문제 접근

N도 20이하라고 주어졌고, 판도 100*100 이라서 어떻게 해도 시간초과가 날 수 없는 구조였다. 그러나, 구현하기가 너무 어려워보이는 문제였다. 주기적으로 간선들을 회전시켜서 새로 배치된 간선을 추가해야 하는데, 이걸 코드로 구현하는데 오래걸렸다. 로직을 계속 실수해서 거의 세시간 가까이 걸린것 같다.

문제 풀이

import java.lang.reflect.Array;
import java.util.*;
import java.io.*;

class Main {

    static boolean[][] graph = new boolean[101][101];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int answer = 0;
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int g = Integer.parseInt(st.nextToken());
            new Dragon(x, y, d, g);
        }

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

class Edge {
    final int x1, y1;
    final int x2, y2;
    final int direct;

    Edge(int x1, int y1, int x2, int y2, int direct) {
        this.x1 = x1;
        this.y1 = y1;
        this.x2 = x2;
        this.y2 = y2;
        this.direct = direct;
    }

    Edge turnNext(Edge sideEdge, Edge changeSideEdge) {
        int nextDirect = (direct + 3) % 4;
        if (x1 == sideEdge.x1 && y1 == sideEdge.y1) {
            if (nextDirect == 0) {
                return new Edge(changeSideEdge.x1, changeSideEdge.y1, changeSideEdge.x1 + 1, changeSideEdge.y1, nextDirect);
            } else if (nextDirect == 1) {
                return new Edge(changeSideEdge.x1, changeSideEdge.y1, changeSideEdge.x1, changeSideEdge.y1 - 1, nextDirect);
            } else if (nextDirect == 2) {
                return new Edge(changeSideEdge.x1, changeSideEdge.y1, changeSideEdge.x1 - 1, changeSideEdge.y1, nextDirect);
            } else {
                return new Edge(changeSideEdge.x1, changeSideEdge.y1, changeSideEdge.x1, changeSideEdge.y1 + 1, nextDirect);
            }
        } else if (x2 == sideEdge.x1 && y2 == sideEdge.y1) {
            if (nextDirect == 0) {
                return new Edge(changeSideEdge.x1 - 1, changeSideEdge.y1, changeSideEdge.x1, changeSideEdge.y1, nextDirect);
            } else if (nextDirect == 1) {
                return new Edge(changeSideEdge.x1, changeSideEdge.y1 + 1, changeSideEdge.x1, changeSideEdge.y1, nextDirect);
            } else if (nextDirect == 2) {
                return new Edge(changeSideEdge.x1 + 1, changeSideEdge.y1, changeSideEdge.x1, changeSideEdge.y1, nextDirect);
            } else {
                return new Edge(changeSideEdge.x1, changeSideEdge.y1 - 1, changeSideEdge.x1, changeSideEdge.y1, nextDirect);
            }
        } else if (x1 == sideEdge.x2 && y1 == sideEdge.y2) {
            if (nextDirect == 0) {
                return new Edge(changeSideEdge.x2, changeSideEdge.y2, changeSideEdge.x2 + 1, changeSideEdge.y2, nextDirect);
            } else if (nextDirect == 1) {
                return new Edge(changeSideEdge.x2, changeSideEdge.y2, changeSideEdge.x2, changeSideEdge.y2 - 1, nextDirect);
            } else if (nextDirect == 2) {
                return new Edge(changeSideEdge.x2, changeSideEdge.y2, changeSideEdge.x2 - 1, changeSideEdge.y2, nextDirect);
            } else {
                return new Edge(changeSideEdge.x2, changeSideEdge.y2, changeSideEdge.x2, changeSideEdge.y2 + 1, nextDirect);
            }
        } else {
            if (nextDirect == 0) {
                return new Edge(changeSideEdge.x2 - 1, changeSideEdge.y2, changeSideEdge.x2, changeSideEdge.y2, nextDirect);
            } else if (nextDirect == 1) {
                return new Edge(changeSideEdge.x2, changeSideEdge.y2 + 1, changeSideEdge.x2, changeSideEdge.y2, nextDirect);
            } else if (nextDirect == 2) {
                return new Edge(changeSideEdge.x2 + 1, changeSideEdge.y2, changeSideEdge.x2, changeSideEdge.y2, nextDirect);
            } else {
                return new Edge(changeSideEdge.x2, changeSideEdge.y2 - 1, changeSideEdge.x2, changeSideEdge.y2, nextDirect);
            }
        }
    }
}

class Dragon {
    ArrayList<Edge> edges = new ArrayList<>();
    int endX, endY;
    final int maxGeneration;
    private int gen = 0;

    Dragon(int x, int y, int direction, int maxGeneration) {
        Main.graph[x][y] = true;
        this.maxGeneration = maxGeneration;
        if (direction == 0) {
            edges.add(new Edge(x, y, x + 1, y, direction));
            Main.graph[x + 1][y] = true;
            endX = x + 1;
            endY = y;
        } else if (direction == 1) {
            edges.add(new Edge(x, y, x, y - 1, direction));
            Main.graph[x][y - 1] = true;
            endX = x;
            endY = y - 1;
        } else if (direction == 2) {
            edges.add(new Edge(x, y, x - 1, y, direction));
            Main.graph[x - 1][y] = true;
            endX = x - 1;
            endY = y;
        } else {
            edges.add(new Edge(x, y, x, y + 1, direction));
            Main.graph[x][y + 1] = true;
            endX = x;
            endY = y + 1;
        }

        next();
    }

    void next() {
        if (this.maxGeneration == this.gen) return;

        ArrayList<Edge> addEdges = new ArrayList<>();
        Edge lastEdge = edges.get(edges.size() - 1);
        Edge firstTurnEdge;
        int nextDirect = (lastEdge.direct + 3) % 4;

        if (endX == lastEdge.x1 && endY == lastEdge.y1) {
            if (nextDirect == 0) {
                firstTurnEdge = new Edge(lastEdge.x1, lastEdge.y1, lastEdge.x1 + 1, lastEdge.y1, nextDirect);
            } else if (nextDirect == 1) {
                firstTurnEdge = new Edge(lastEdge.x1, lastEdge.y1, lastEdge.x1, lastEdge.y1 - 1, nextDirect);
            } else if (nextDirect == 2) {
                firstTurnEdge = new Edge(lastEdge.x1, lastEdge.y1, lastEdge.x1 - 1, lastEdge.y1, nextDirect);
            } else {
                firstTurnEdge = new Edge(lastEdge.x1, lastEdge.y1, lastEdge.x1, lastEdge.y1 + 1, nextDirect);
            }
        } else {
            if (nextDirect == 0) {
                firstTurnEdge = new Edge(lastEdge.x2 - 1, lastEdge.y2, lastEdge.x2, lastEdge.y2, nextDirect);
            } else if (nextDirect == 1) {
                firstTurnEdge = new Edge(lastEdge.x2, lastEdge.y2 + 1, lastEdge.x2, lastEdge.y2, nextDirect);
            } else if (nextDirect == 2) {
                firstTurnEdge = new Edge(lastEdge.x2 + 1, lastEdge.y2, lastEdge.x2, lastEdge.y2, nextDirect);
            } else {
                firstTurnEdge = new Edge(lastEdge.x2, lastEdge.y2 - 1, lastEdge.x2, lastEdge.y2, nextDirect);
            }
        }


        addEdges.add(firstTurnEdge);
        Main.graph[firstTurnEdge.x1][firstTurnEdge.y1] = true;
        Main.graph[firstTurnEdge.x2][firstTurnEdge.y2] = true;

        for (int i = edges.size() - 2; i >= 0; i--) {
            firstTurnEdge = edges.get(i).turnNext(edges.get(i + 1), firstTurnEdge);
            addEdges.add(firstTurnEdge);
            Main.graph[firstTurnEdge.x1][firstTurnEdge.y1] = true;
            Main.graph[firstTurnEdge.x2][firstTurnEdge.y2] = true;
        }

        edges.addAll(addEdges);

        Edge le = edges.get(edges.size() - 1);
        Edge pveLe = edges.get(edges.size() - 2);
        if (le.x1 == pveLe.x1 && le.y1 == pveLe.y1) {
            endX = le.x2;
            endY = le.y2;
        } else if (le.x1 == pveLe.x2 && le.y1 == pveLe.y2) {
            endX = le.x2;
            endY = le.y2;
        } else if (le.x2 == pveLe.x1 && le.y2 == pveLe.y1) {
            endX = le.x1;
            endY = le.y1;
        } else {
            endX = le.x1;
            endY = le.y1;
        }

        gen++;
        next();
    }
}

시물레이션 문제가 처음이라서 진짜 코드로 표현하는 과정에서 머리가 좀 어지러워서 딴 짓도 많이했다...
다른 사람들의 풀이를 보니 내 코드의 거의 절반이던데....
한 번 비교해보고 알게된 점을 아래에 추가할 예정이다.
다만, 이게 프로그래머스 환경이였다면 디버깅을 못해서 못풀었을 것 같다. 구현 및 시뮬레이션 문제를 많이 풀어봐야겠다.