BOJ_3190 : 뱀

👉 문제링크

3190번: 뱀

---

🔸 문제 분석 🔸

• NxN 게임판에서 뱀이 이동하는 게임이 몇초간 진행 되는지 반환한다.
• 게임 판에는 K개의 사과가 있고, 사과를 먹으면 몸 길이가 1 늘어나며 기존의 꼬리 위치가 변경되지 않는다.
• 몸 혹은 게임판 벽에 부딪히면 게임이 종료된다.

🔸 문제 풀이 🔸

• 특별한 알고리즘이 없는 시뮬레이션 문제이다.
• 뱀의 방향 전환 정보와 뱀의 꼬리 좌표를 기억하기 위해 큐 자료구조를 사용한다.

🔸 코드 🔸

import java.io.*;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = null;

        byte N = Byte.parseByte(br.readLine());
        byte[][] board = new byte[N + 1][N + 1]; // 게임판

        byte K = Byte.parseByte(br.readLine());

        for (int i = 0; i < K; i++) { // 사과 위치 기록 : 1
            st = new StringTokenizer(br.readLine());
            board[Byte.parseByte(st.nextToken())][Byte.parseByte(st.nextToken())] = 1;
        }

        byte L = Byte.parseByte(br.readLine());
        Queue<Turn> que = new ArrayDeque<>(); // 회전 정보 저장

        for (int i = 0; i < L; i++) { // 회전 정보 기록
            st = new StringTokenizer(br.readLine());
            que.add(new Turn(Short.parseShort(st.nextToken()), st.nextToken().charAt(0) == 'L' ? (byte) 3 : (byte) 1));
        }

        // Play
        int answer = playDummy(board, que);

        // Output
        bw.write(Integer.toString(answer));
        bw.flush();
    }

    private static int playDummy(byte[][] board, Queue<Turn> que) {
        // 방향 정보 초기화
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};
        int direction = 1; // 뱀은 오른쪽을 보고 시작

        // 좌표 정보 초기화
        Position now = new Position(1, 1);
        board[1][1] = 2;

        // 꼬리 정보
        Queue<Position> tail = new ArrayDeque<>();
        tail.add(new Position(1, 1));

        Turn turn = que.poll();

        int time = 0;

        while (true) {
            // 시간 증가
            time++;


            // 이동
            now.row += dx[direction];
            now.col += dy[direction];

            // 방향 변경
            if (time == turn.X) {
                direction = (direction + turn.C) % 4;
                if (!que.isEmpty()) {
                    turn = que.poll();
                }
            }

            // 게임판 벗어나면 종료
            if (now.row <= 0 || board.length <= now.row || now.col <= 0 || board[0].length <= now.col) {
                return time;
            }

            if (board[now.row][now.col] == 0) { // 일반 이동
                board[now.row][now.col] = 2;
                if (!tail.isEmpty()) { // 꼬리 없앰
                    Position tp = tail.poll();
                    board[tp.row][tp.col] = 0;
                }
                tail.add(new Position(now.row, now.col));
            } else if (board[now.row][now.col] == 1) { // 사과 먹음
                board[now.row][now.col] = 2;
                tail.add(new Position(now.row, now.col));
            } else { // 뱀 몸에 부딪힘
                return time;
            }
        }
    }

    private static class Position {
        int row, col;

        public Position(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }

    private static class Turn {
        short X;
        Byte C;

        public Turn(short x, Byte c) {
            X = x;
            C = c;
        }
    }
}

🔸 코드 해석 🔸

• 코드의 흐름은 주석으로 잘 정리되어 있으니, 간단한 흐름만 설명한다.
  • 게임판에 사과 위치 정보를 기록한다.
  • 방향 전환 정보를 큐에 넣는다.
  • 게임을 진행하며 꼬리 좌표를 큐에 넣는다.
  • 게임판을 벗어나거나 몸에 부딪히면 게임을 종료한다.
• 이동 후에 방향을 변경하는 점을 유의한다.

---

🔸 end 🔸

• 단순 구현 문제여서 크게 어려운 부분은 없었다.
  • 문제에서 자세히 설명되어 지지 않은 것 같은데, 뱀의 이동 이후에 방향이 변경되는 부분이 있어서 테스트 케이스를 보고 조금 디버깅 할 필요가 있었다.
• 입력 값이 100 이하인 부분이 많아서 갑자기 메모리를 아껴서 구현해 보고 싶었다.
  • -128~127 까지 사용 가능한 Byte와 X만 값이 커서 Short를 사용해서 구현해보았다.
  • 하지만 NumberFormatException이 떠서 그냥 전부 int로 바꿔보니 통과 되었다.
  • 뭐가 문제인가 다시 살펴보니 X만 Short형인데 Byte로 입력을 변환한게 문제였다.
  • 역시 코딩 테스트에서는 이렇게 메모리를 아끼진 않아도 되니 int 혹은 long을 쓰는게 맞는 것 같다.