[Backjoon] 뱀

프로그래밍 문제 중에서 나한테 부담이 큰 부분은 구현 문제들이다. 여러 조건들을 차례대로 구현하기만 하면 되는 문제들이지만 긴장된 상태에서 허겁지겁 문제를 읽다보면 실수가 많이 발생한다. 이번 문제를 풀 때에도 실제 테스트도 아닌데 그런 묘한 긴장감이 있었다.
구현 문제를 접근 할 때에는 반드시 주석으로 의사코드를 작성하고 접근해야한다. 이번 문제도 그런 접근이 효과적이었다. 문제의 조건은 아래와 같다.

- 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
- 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
- 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

자칫 겁먹을 수도 있는 문제인데 가만히 생각해보면 큐 자료구조를 사용하면 쉽게 해결할 수 있다. 아래는 파이썬으로 구현한 소스이다.

 

import sys

if __name__ == "__main__":
    board_size = int(sys.stdin.readline())
    board = [[0 for _ in range(board_size)] for _ in range(board_size)]

    apple_count = int(sys.stdin.readline())
    for _ in range(apple_count):
        row, col = list(map(int, sys.stdin.readline().split(" ")))
        board[row-1][col-1] = 1

    move_commands = []
    commands_count = int(sys.stdin.readline())
    for _ in range(commands_count):
        second, command = sys.stdin.readline().replace("\n", "").split(" ")
        move_commands.append([int(second), command])

    # 오른쪽 회전일 경우 idx + 1, 왼쪽 회전일 경우 idx - 1
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    idx_direction = 0
    x_position, y_position = 0, 0

    score = 0
    snake = [[0, 0]]
    while 0 <= y_position < board_size and 0 <= x_position < board_size:
        # 커맨드 조건에 맞는다면
        if move_commands and move_commands[0][0] == score:
            if move_commands[0][1] == "D":
                idx_direction += 1
            elif move_commands[0][1] == "L":
                idx_direction -= 1
            
            if idx_direction > 3:
                idx_direction = 0
            elif idx_direction < 0:
                idx_direction = 3
            move_commands.pop(0)
            
        # 머리 다음칸 이동
        board[y_position][x_position] = 2
        x_position += dx[idx_direction]
        y_position += dy[idx_direction]
        score += 1

        if 0 > y_position or board_size <= y_position or 0 > x_position or board_size <= x_position:
            break

        if board[y_position][x_position] == 2:
            break

        # 이동한 칸에 사과가 없었다면
        if board[y_position][x_position] != 1:
            # 꼬리 위치 초기화
            y, x = snake[0]
            board[y][x] = 0
            snake.pop(0)
        snake.append([y_position, x_position])

    print(score)