[백준/BOJ] #3190 뱀.python(파이썬)

문제 링크 / 출처

https://www.acmicpc.net/problem/3190

3190번: 뱀

 

문제 요약

잘 알려진 뱀게임에서, 주어진 커맨드를 수행했을 때 게임이 끝나는 시간을 구하는 문제

[제약사항]

• 2 ≤ N ≤ 100
• 0 ≤ K ≤ 100
• 1 ≤ L ≤ 100
• 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전
• X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.

 

풀이

머리의 움직임이 몸길이 만큼의 시간이 지난 후에 꼬리의 움직임에 반영된다는 점에서 큐를 사용해야겠다고 생각했고,

 

큐를 응용해서 문제를 풀이했다.

 

직접적으로 큐로 사용하는 리스트의 값을 삭제하지는 않고, head와 tail 두개의 idx를 사용해 큐를 구현했다.

 

코드

# 뱀

import sys

input = sys.stdin.readline

N = int(input())  # 보드의 크기
K = int(input())  # 사과의 개수
apples = [list(map(int, input().split())) for _ in range(K)]  # 사과의 좌표

L = int(input())                                    # 방향전환 횟수
moves = [input().split() for _ in range(L)]         # 시간, 뱀의 방향전환
direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]      # 우하좌상
board = [[1] * (N + 1) for _ in range(N + 1)]       # 좌상단 == (1,1)

for r, c in apples:             # 사과의 위치 표시
    board[r][c] = 2

snake_body = [(1, 1)]           # 뱀의 위치 좌표
head, tail = 0, 0
move_idx = 0
move_direction = 0              # 뱀의 시작 방향
game_time = 0                   # 게임 시간

hr, hc = snake_body[head]       # 머리의 위치
while True:
    game_time += 1
    dr, dc = direction[move_direction]
    snake_body.append((hr + dr, hc + dc))
    head += 1                   # 앞으로 한칸 전진
    hr, hc = snake_body[head]   # 머리의 위치
    tr, tc = snake_body[tail]   # 꼬리의 위치

    # 0: 뱀, 1: 빈칸, 2: 사과
    if 0 < hr <= N and 0 < hc <= N and board[hr][hc]:
        if board[hr][hc] == 1:
            board[tr][tc] = 1
            tail += 1
        board[hr][hc] = 0
    else:
        break

    if move_idx < L and int(moves[move_idx][0]) == game_time:
        if moves[move_idx][1] == 'D':
            move_direction = (move_direction + 1) % 4
        else:
            move_direction = (move_direction + 3) % 4
        move_idx += 1

print(game_time)