백준 3190번 뱀 JAVA

링크텍스트

설명

풀이 흐름 설명

시뮬레이션 문제이므로 문제에서 제시한 순서를 그대로 구현하였다.
먼저 보드의 크기와 사과의 위치를 입력받아 2차원 배열에 저장하였다.
이후 방향 전환 정보를 시간 기준으로 배열에 저장하였다.

뱀의 몸은 Deque를 사용하여 관리하였다.
머리는 앞에 추가하고 꼬리는 뒤에서 제거하는 방식으로 구현하였다.
또한 자기 몸과의 충돌을 O(1)에 확인하기 위해 body 배열을 따로 두어 현재 뱀이 차지하고 있는 위치를 표시하였다.

시뮬레이션은 1초씩 증가시키며 반복하도록 구현하였다.
매 초마다 현재 방향으로 한 칸 이동하도록 하였다.
이동한 위치가 벽이거나 body 배열이 true라면 즉시 종료하도록 처리하였다.

고민과 해결

가장 먼저 고민한 부분은 자기 몸에 부딪혔을 때 어떻게 처리할 것인지였다.
Deque만 사용할 경우 몸 전체를 순회하며 확인해야 하므로 비효율적이라고 판단하였다.
이를 해결하기 위해 body 2차원 배열을 추가로 사용하여 현재 위치가 몸인지 즉시 확인하도록 구현하였다.

두 번째 고민은 몸 길이를 어떻게 늘릴 것인지였다.
사과를 먹은 경우에는 꼬리를 제거하지 않으면 길이가 자연스럽게 증가한다는 점을 이용하였다.
사과가 없는 경우에만 removeLast()를 호출하여 꼬리를 제거하도록 하였다.

또한 방향 전환을 구현할 때 왼쪽 회전과 오른쪽 회전을 어떻게 계산할지 고민하였다.
방향을 0~3으로 정의하고 왼쪽은 (dir + 3) % 4, 오른쪽은 (dir + 1) % 4로 처리하여 시계/반시계 회전을 간단히 구현하였다.

어떻게 더 최적화할 수 있나

현재 구현은 매 초마다 모든 연산을 O(1)로 처리하도록 구성하였다.
Deque를 사용하여 머리 추가와 꼬리 제거를 상수 시간에 처리하였다.
또한 body 배열을 두어 충돌 체크를 상수 시간에 수행하도록 하였다.

만약 body 배열 없이 Deque만 사용하였다면 자기 몸 충돌 검사에 O(N)이 발생하여
최악의 경우 시간 복잡도가 크게 증가했을 것이다.
따라서 현재 구조가 이미 최적에 가깝다고 판단하였다.

추가적으로 방향 전환 정보를 Map 대신 배열과 인덱스로 관리하여
불필요한 탐색 없이 시간 증가에 따라 바로 확인하도록 구성하였다.

시간복잡도: O(T), 공간복잡도: O(N²)

회독

• [ x ] 1회
• 2회
• 3회

코드

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

public class Main {
        static int n,k;
        static int [][] arr;
        static boolean [][] apples;
        static int [] dx = {0,1,0,-1}; // 우, 하, 좌, 상 (시계 방향)
        static int [] dy = {1,0,-1,0};
        static Snake [] snakes;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());
        
        arr = new int[n+1][n+1];
        apples = new boolean[n+1][n+1];
        
        for(int i=0;i<k;i++){
            st = new StringTokenizer(br.readLine());

            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            apples[r][c] = true;
        }

        int l = Integer.parseInt(br.readLine());
        snakes = new Snake[l];
        for(int i=0;i<l;i++){
            st = new StringTokenizer(br.readLine());
            int seconds = Integer.parseInt(st.nextToken());
            char turn = st.nextToken().charAt(0);

            snakes[i] = new Snake(seconds, turn);
        }

        System.out.println(simulation(1,1));
    }
    
    public static int simulation(int x, int y){
        Deque<int []> dq = new ArrayDeque<>();
        boolean [][] body = new boolean[n+1][n+1];

        int dir = 0; // 처음 오른쪽
        int time = 0;
        int idx = 0; // 방향 전환 인덱스

        dq.add(new int[]{x,y});
        body[x][y] = true;

        while(!dq.isEmpty()){
            time++;

            int xx = x+dx[dir];
            int yy = y+dy[dir];

            if(xx<1 || xx>n || yy<1 || yy>n || body[xx][yy]) break;

            dq.addFirst(new int[]{xx,yy});
            body[xx][yy] = true;

            if(apples[xx][yy]){
                apples[xx][yy] = false;
            }else{
                int [] tail = dq.removeLast();
                body[tail[0]][tail[1]] = false;
            }

            x = xx;
            y = yy;

            if(idx<snakes.length && time == snakes[idx].seconds){
                if(snakes[idx].turn=='L'){
                    dir = (dir+3)%4;
                }else{
                    dir = (dir+1)%4;
                }
                idx++;
            }
        }

        return time;
    }

    static class Snake{
        int seconds;
        char turn;

        Snake(int seconds, char turn){
            this.seconds = seconds;
            this.turn = turn;
        }
    }
}