[ 백준 3190번 ] 뱀

1. 문제

3190번: 뱀

 

2. 풀이

구현/시뮬레이션 유형의 문제로, 우선 문제를 꼼꼼하게 이해하는 것이 무엇보다 중요한 문제다. 뱀의 움직임은 크게 아래와 같이 세 가지 유형으로 분리해서 생각할 수 있다.

 

1) 더 움직일 수 없는 경우

지도에서 벗어나려 하거나 움직이고자 하는 칸에 뱀의 몸뚱이가 있는 경우 게임은 종료된다.

 

2) 사과를 먹는 경우

사과를 먹는 경우 몸 길이가 1 늘어나게 된다. 문제에서는 복잡하게 설명하였으나, 다음칸으로 전진한 머리를 유지하고 꼬리는 삭제되지 않는다는 것은 뱀의 길이가 1 늘어났다고 봐도 무방하다.

 

3) 사과를 먹지 않는 경우

'몸길이가 변하지 않는다'는 말이 오히려 혼선을 주는 것 같은데, 실질적으로는 한 칸 앞으로 이동한다고 받아들이는 것이 개인적으로는 이해하기 쉬웠다.

 

---

 

이 세 가지 유형을 구현함에 있어 가장 중요한 것은 바로 문제에서 제시한 첫 번째 조건인 뭐가 됐든 머리는 한 칸 앞으로 간다는 것이다. 다만, 머리가 이동한 자리에 사과가 있는 경우에는 꼬리를 유지해서 길이를 늘려주고, 그렇지 않은 경우에는 꼬리를 제거함으로써 이동만 시킨다는 것이다. 여기서 이동만 시킨다는 것을 보다 직관적으로 얘기하자면, 머리를 추가하고 꼬리를 제거하면 형상은 유지된 상태로 진행방향으로 움직이기만 했다는 것이다.

 

즉, 이 과정을 돌아보면 데이터(뱀의 머리와 꼬리)의 입출력이 양 쪽 끝에서만 발생한다는 것을 알 수 있다. 우리는 그에 가장 적합한 자료구조인 Deque를 이용해 구현하면 된다는 결론에 도달할 수 있게 된다.

 

이 때, 진행된 게임의 시간에 따라서 방향을 전환시켜주는 부분만 추가적으로 잘 구현해준다면 해결할 수 있다.

 

3. 소스코드

public class Main {
    static final int APPLE = 1, SNAKE = 2;
    static final int[] dy = {-1, 0, 1, 0};
    static final int[] dx = {0, 1, 0, -1};
    static int N;
    static int[][] map;
    static char[] query = new char[10001];

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

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        
        // 좌표가 (1, 1) -> (N, N)으로 되어 있으므로 입력에서 1씩 빼준다.
        int K = Integer.parseInt(br.readLine());
        while (K-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            map[Integer.parseInt(st.nextToken()) - 1][Integer.parseInt(st.nextToken()) - 1] = APPLE;
        }
        
        // 특정 시간대에 방향을 전환하기 위해 시간대에 방향전환 쿼리를 입력해둔다.
        int L = Integer.parseInt(br.readLine());
        while (L-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            query[Integer.parseInt(st.nextToken())] = st.nextToken().charAt(0);
        }

        Snake snake = new Snake();

        bw.write(snake.moveAndGetTime() + "");
        bw.close();
        br.close();
    }

    static class Snake {
        int dir = 1;
        Deque<Integer> deque = new LinkedList<>();
        
        // (0, 0)에서 시작하도록 초기화
        public Snake() {
            deque.add(0);
            map[0][0] = SNAKE;
        }

        int moveAndGetTime() {
            int time = 0;

            while (true) {
                time++;
                
                // 머리가 다음으로 이동할 칸을 체크
                int ny = deque.peekFirst() / N + dy[dir];
                int nx = deque.peekFirst() % N + dx[dir];

                if (ny < 0 || nx < 0 || N <= ny || N <= nx || map[ny][nx] == SNAKE) break;

                // 사과가 있다면 머리를 추가해줌
                if (map[ny][nx] == APPLE) {
                    map[ny][nx] = SNAKE;
                    deque.addFirst(ny * N + nx);
                } else { // 사과가 없다면 꼬리를 제거하고 해당 칸을 0으로 초기화해줌
                    map[ny][nx] = SNAKE;
                    map[deque.peekLast() / N][deque.peekLast() % N] = 0;
                    deque.pollLast();
                    deque.addFirst(ny * N + nx);
                }
                
                // 방향 전환이 필요한 게임 시간이라면 방향을 바꿔줌
                if (time <= 10000 && (query[time] == 'L' || query[time] == 'D')) rotate(query[time]);
            }

            return time;
        }
        
        // 배열 idx 모듈러 연산을 통해 방향을 시프트 처리
        private void rotate(char type) {
            dir = type == 'L'
                    ? (dir + 3) % 4
                    : (dir + 1) % 4;
        }
    }

}

GitHub - kwanik-kor/BOJ: Baekjoon Online Judge - explanation of solved problems and complete code