백준 3190번 뱀: C언어 풀이

백준 3190 뱀 문제의 C언어 해설입니다.
뱀을 덱 자료구조를 사용해 모델링하고, 타일의 상태와 뱀의 방향 전환을 구현하기 위한 전략을 설명합니다.

전략

뱀을 덱으로 구성한다.

뱀이 이동 할 때마다 머리/꼬리에서 삽입/삭제가 발생한다.
따라서 뱀을 덱으로 구성하는 게 합리적이다.

덱의 원소는 NxN 보드 위 타일을 가르키는 포인터로 두었다.
보드 위의 좌표(i, j)를 저장하는 것보다 직관적인것 같다.

타일의 구성

타일은 다음과 같은 4가지 상태 중 하나를 갖는다.

1. 평원: 아무것도 없는 기본 상태이다.
2. 사과: 여기에는 사과가 놓여있다.
3. 뱀: 여기에는 뱀이 놓여져있다.
4. 공허: NxN 보드의 바깥 공간을 의미한다.

이를 전부 enum으로 정의하기로 한다.

여기서 굳이 4번, 공허 타일을 추가한 이유는 경계값 처리를 간단하게 하기 위함이다.
보드의 바깥에 닿았을 때 게임 오버가 되어야 하니까, 그냥 공허 타일에 도달하면 게임 오버가 되도록 하면 된다.
문제의 입력값이 1-based indexing으로 주어지기 때문에 입력값을 받는 것도 편리해진다.

뱀의 회전 구현

뱀이 나아가는 방향을 오른쪽, 아래쪽, 왼쪽, 윗쪽 순서대로 0, 1, 2, 3 으로 정의한다.

이러면

우측 회전은 기존 방향을 +1
왼쪽 회전은 기존 방향을 -1 하는 것으로 구현 가능하다.

3+1 = 4로 범위를 벗어나더라도 4로 나눠주면 된다.

회전의 가짓수가 2의 거듭제곱이기 떄문에 3과의 bitwise and 를 통해 빠르게 나머지를 구할 수도 있다.

코드

#include <stdio.h>

#define MAX_BOARD_SIZE 102
#define MAX_SNAKE_SIZE 128
#define SNAKE_MASK 127
#define MAX_GAME_TIME 10000
#define TURN_MASK 3

enum snake_direction
{
    RIGHT = 0,
    DOWN,
    LEFT,
    UP
};

enum tile_state
{
    VOID = 0,
    PLAIN = 1,
    APPLE = 2,
    SNAKE = 3,
};

enum rotation_state
{
    NO_ROTATION = '\0',
    RIGHT_TURN = 'D',
    LEFT_TURN = 'L'
};

enum tile_state board[MAX_BOARD_SIZE][MAX_BOARD_SIZE];

enum tile_state *snake[MAX_SNAKE_SIZE];
int tail = 0;
int head = 0;

enum rotation_state rotations[MAX_GAME_TIME];

int main(void)
{
    int board_size;
    scanf("%d", &board_size);

    // Fill the board with plain tiles
    for (int j = 1; j <= board_size; j++)
    {
        for (int i = 1; i <= board_size; i++)
        {
            board[i][j] = PLAIN;
        }
    }

    // Apples
    int num_apples;
    scanf("%d", &num_apples);
    int row, col;
    for (int i = 0; i < num_apples; i++)
    {
        scanf("%d %d", &row, &col);
        board[row][col] = APPLE;
    }

    int num_rotations;
    scanf("%d", &num_rotations);

    // Rotations
    int time;
    char rotation;
    for (int i = 0; i < num_rotations; i++)
    {
        scanf("%d %c", &time, &rotation);
        rotations[time] = rotation;
    }

    // Initialize
    int game_time = 0;
    board[1][1] = SNAKE;
    snake[head++] = &board[1][1];
    enum snake_direction direction = RIGHT;

    int next_tile_i = 1;
    int next_tile_j = 1;
    while (1)
    {
        // Turn
        switch (rotations[game_time])
        {
            case RIGHT_TURN:
                direction = (direction + 1) & TURN_MASK;
                break;
            case LEFT_TURN:
                direction = (direction - 1) & TURN_MASK;
                break;
            case NO_ROTATION:
                break;
        }

        // Move
        switch (direction)
        {
            case RIGHT:
                next_tile_j++;
                break;
            case DOWN:
                next_tile_i++;
                break;
            case LEFT:
                next_tile_j--;
                break;
            case UP:
                next_tile_i--;
                break;
        }
        game_time++;

        // Check the next tile
        switch (board[next_tile_i][next_tile_j])
        {
            // Game over
            case VOID:
            case SNAKE:
                printf("%d", game_time);
                return 0;
                break;

            case PLAIN:
                // Push
                board[next_tile_i][next_tile_j] = SNAKE;
                snake[head] = &board[next_tile_i][next_tile_j];
                head = (head + 1) & SNAKE_MASK;
                // Pop
                *snake[tail] = PLAIN;
                tail = (tail + 1) & SNAKE_MASK;
                break;

            case APPLE:
                // Push
                board[next_tile_i][next_tile_j] = SNAKE;
                snake[head] = &board[next_tile_i][next_tile_j];
                head = (head + 1) & SNAKE_MASK;
                break;
        }
    }
}