10875. 뱀

Problem 💻

이 문제는 L ≤ 10^8 이므로 2차원 배열을 만들어 하나하나 뱀을 이동시켜가며 풀 수 있는 문제는 아니다. 그러므로 머리의 회전 횟수 N을 이용해 문제를 해결해야 한다.

 

 

Approach 1 ⭕

• 구현

해당 문제는 뱀이 머리를 1초마다 하나씩 늘려가며 어떤 시간에는 회전도 하고 하면서 최종 죽는 시간을 구하는 문제이다. 문제의 주체를 뱀이 아니라 사람이라고 생각하면 자신이 가던 경로와 겹치는 순간 혹은 범위의 밖으로 가는 순간 죽는 것으로 해석할 수 있다.

 

뱀은 오로지 수직, 수평으로만 머리가 늘어난다. 그래서 방향을 바꾸는 시간 차이와 바꾸는 방향이 주어지면 바꾸는 시간 전까지는 같은 방향으로만 이동한다. 그래서 해당 방향 전까지 하나하나 이동하지 않고 단번에 ‘x + time’ 또는 ‘y + time’으로 좌표를 결정할 수 있다.

 

이러한 좌표를 활용해 수직 경로에 대해서 상하좌우로 부딪혔을 경우, 수평 경로에 대해서 상하좌우로 부딪혔을 경우를 모두 생각하여 구현하면 된다. 그리고, 마지막으로 방향을 바꾸었을 때 뱀이 죽지 않고 계속 나아갈 수 있으므로 모든 방향 전환을 마치고 뱀이 더 이동할 수 있는지를 보면 된다.

 

하지만, 어려운 것.. 못 풀었다 ㅜ

 

여러 풀이 방법이 있겠지만, 내가 본 풀이 방법은 수직, 수평일 때 상하좌우로 다가가는 경로의 시작 점과 본래 경로의 시작 점 사이의 차이 중 작은 값을 고르고 해당 값이 방향을 회전하는 시간의 차이보다 크면 부딪힌 것이고 작으면 부딪히지 않은 것!

 

 

이전의 수평 경로를 아래에서 위로 부딪히는 경우(상하좌우 중 상)를 그림으로 보면 위와 같다. time 즉, 방향을 바꾸기 전 현재 움직이던 경로를 모두 움직인 경우의 길이와 현재 경로의 시작점과 수평 경로의 차이 중 해당 경로를 모두 움직인 경우가 더 크다면, 무조건 부딪히게 되어 있고 작으면 부딪히지 않는다!

 

이걸 8가지 경우에 모두 생각해서 적용해주면 정답이 된다.

 

Solution 💡

public class BOJ_10875 {

    private static int[] dy = {0, 1, 0, -1};
    private static int[] dx = {1, 0, -1, 0};

    private static class Command {
        long time;
        char cmd;

        public Command(long time, char cmd) {
            this.time = time;
            this.cmd = cmd;
        }
    }

    private static class Snake {
        long sy, sx;
        long ey, ex;

        public Snake(long sy, long sx, long ey, long ex) {
            this.sy = sy;
            this.sx = sx;
            this.ey = ey;
            this.ex = ex;

            if (this.sy > this.ey) {
                long tmp = this.sy;
                this.sy = this.ey;
                this.ey = tmp;
            }
            if (this.sx > this.ex) {
                long tmp = this.sx;
                this.sx = this.ex;
                this.ex = tmp;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int l = Integer.parseInt(br.readLine());
        int n = Integer.parseInt(br.readLine());
        ArrayList<Command> cmd = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long time = Long.parseLong(st.nextToken());
            char c = st.nextToken().charAt(0);

            cmd.add(new Command(time, c));
        }

        ArrayList<Snake> snakes = new ArrayList<>();
        snakes.add(new Snake(-l-1, -l-1, l+1, -l-1));
        snakes.add(new Snake(l+1, -l-1, l+1, l+1));
        snakes.add(new Snake(l+1, l+1, -l-1, l+1));
        snakes.add(new Snake(-l-1, l+1, -l-1, -l-1));
        long y = 0;
        long x = 0;
        int dir = 0;

        long ret = 0;

        boolean done = false;
        Command command;
        for (int i = 0; i < cmd.size()+1; i++) {
            if (i == cmd.size()) {
                command = new Command(Long.MAX_VALUE, 'L');
            } else {
                command = cmd.get(i);
            }

            long t = Long.MAX_VALUE;
            for (int idx = 0; idx < snakes.size(); idx++) {
                if (snakes.get(idx).ey == snakes.get(idx).sy) {
                    if (dir == 0) { // 오른
                        if (y == snakes.get(idx).ey && x < snakes.get(idx).sx)
                            t = Math.min(t, snakes.get(idx).sx - x);
                    } else if (dir == 1) { // 위
                        if (snakes.get(idx).sx <= x && x <= snakes.get(idx).ex && y < snakes.get(idx).sy)
                            t = Math.min(t, snakes.get(idx).sy - y);
                    } else if (dir == 2) { // 왼
                        if (snakes.get(idx).ey == y && x > snakes.get(idx).ex)
                            t = Math.min(t, x - snakes.get(idx).ex);
                    } else { // 아래
                        if (snakes.get(idx).sx <= x && x <= snakes.get(idx).ex && y > snakes.get(idx).sy)
                            t = Math.min(t, y - snakes.get(idx).sy);
                    }
                } else if (snakes.get(idx).ex == snakes.get(idx).sx) {
                    if (dir == 0) {
                        if (snakes.get(idx).sy <= y && y <= snakes.get(idx).ey && x < snakes.get(idx).sx)
                            t = Math.min(t, snakes.get(idx).sx - x);
                    } else if (dir == 1) {
                        if (snakes.get(idx).sx == x && y < snakes.get(idx).sy)
                            t = Math.min(t, snakes.get(idx).sy - y);
                    } else if (dir == 2) {
                        if (snakes.get(idx).ey >= y && y >= snakes.get(idx).sy && x > snakes.get(idx).sx)
                            t = Math.min(t, x - snakes.get(idx).sx);
                    } else {
                        if (snakes.get(idx).sx == x && y > snakes.get(idx).ey)
                            t = Math.min(t, y - snakes.get(idx).ey);
                    }
                }
            }

            if (command.time < t) {
                snakes.add(new Snake(y, x, y + dy[dir] * command.time, x + dx[dir] * command.time));
                ret += command.time;
                y = y + dy[dir] * command.time;
                x = x + dx[dir] * command.time;

                if (command.cmd == 'L') dir = (dir + 1) % 4;
                else dir = (dir - 1 < 0) ? 3 : dir - 1;
            } else {
                ret += t;
                break;
            }
        }

        System.out.println(ret);
    }
}