문제

'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
• 사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

코드

import sys
from collections import deque
input = sys.stdin.readline

# 각 방향을 지정
East = (1,0)
West = (-1, 0)
South = (0, 1)
North = (0, -1)


n = int(input()) #맵의 크기

apple = int(input())# 사과의 갯수
apples = deque()#사과의 위치
for j in range(apple):
    row, col = map(int, input().split())
    apples.append((col, row)) #문제에는 row,col로 되어있는데 예시는 col,row임

cmd = int(input()) #방향 조정할 시간
queue = deque()
for a in range(cmd):
    queue.append(list(map(str, input().split())))

front = (1,1)
loc = deque()
loc.append(front)
dir = East
cnt = 0
while True:
    if queue and int(queue[0][0]) == cnt: #시간에 맞춰서 방향 조정
        if queue[0][1] == 'D':
            if dir == East:
                dir = South
            elif dir == West:
                dir = North
            elif dir == South:
                dir = West
            elif dir == North:
                dir = East

        elif queue[0][1] == 'L':
            if dir == East:
                dir = North
            elif dir == West:
                dir = South
            elif dir == South:
                dir = East
            elif dir == North:
                dir = West

        queue.popleft()

    move = (front[0]+ dir[0], front[1]+dir[1]) #뱀의 머리 부분의 위치 갱신
    cnt += 1 #1초
    if move in loc: #뱀의 몸통과 머리가 부딪힐 때
        break
    else:
        loc.append(move)
    if move not in apples: #이동하는 위치에 사과가 없을 때
        loc.popleft()
    else:# 사과가 있을 때
        apples.remove(move)
    front = loc[-1]
    #맵을 벗어날 때
    if move[0] > n or move[1] > n or move[0] < 1 or move[1] < 1:
        break

print(cnt)

설명

사과의 위치(apples)와 뱀의 좌표(loc)를 큐로 선언하고 매 초다마다 각 방향에 맞는 좌표 값을 move에 갱신해준다. 사과를 안먹었다면 popleft하지 않는다. 시간(cnt)가 주어진 방향 전환을 해야되는 시간과 같으면 방향을 조정해주고 갱신되는 좌표가 맵을 벗어나거나 뱀의 몸통과 머리가 부딪힌다면 break해준다.