뭐였더라

큐를 이용한 구현 문제다. 큐에 뱀의 다음 머리 위치를 저장하고 꼬리 부분을 pop 시키면서 반복문을 돌아준다. 

from collections import deque

# rotation 행렬
L_rotate = [[0, 1], 
            [-1, 0]]
R_rotate = [[0, -1],
            [1, 0]]


N = int(input())
K = int(input())
apples = [list(map(int, input().split())) for _ in range(K)]
L = int(input())
turns = [list(input().split()) for _ in range(L)]

# 전체 보드
board = [[0 for _ in range(N)]
         for _ in range(N)]
# 시작 위치는 가장 왼쪽 상단이다. 뱀을 2로 둔다.
board[0][0] = 2

# 사과는 1로 둔다.
for i, j in apples:
    board[i-1][j-1] = 1

q = deque([[0, 0]]) # 시작 위치와 회전하는 시간을 큐로 저장한다.
turn = deque(turns)
move = [1, 0] # 시작 방향은 오른쪽이다.
t = 0

while q:
	# 뱀 머리 위치는 큐 가장 끝에 있다.
    x, y = q[-1]
    nx = x + move[0] # 다음 방향 설정
    ny = y + move[1] 
    t += 1

    if (0 <= nx < N and 0 <= ny < N): # 보드 내부에서만 이동
        if board[ny][nx] == 2: # 다음 위치가 뱀의 몸과 충돌한다면 종료
            break
        else:
            if board[ny][nx] == 0: # 빈 공간이라면
                x, y = q.popleft() # 꼬리 위치 pop
                board[y][x] = 0 # 꼬리 위치 빈 공간으로
            q.append([nx, ny]) # 큐에 다음 머리 위치 추가
            board[ny][nx] = 2 # 머리 이동
    else: # 보드 밖으로 나간다면 종료
        break

    if turn: # 아직 회전할게 남았다면
        time, direction = turn.popleft() # 시간과 방향 pop
        if t == int(time): 회전할 시간이라면
            if direction == 'L': # 방향에 맞게 회전
                x_move = L_rotate[0][0] * move[0] + L_rotate[0][1] * move[1]
                y_move = L_rotate[1][0] * move[0] + L_rotate[1][1] * move[1]
            else:   
                x_move = R_rotate[0][0] * move[0] + R_rotate[0][1] * move[1]
                y_move = R_rotate[1][0] * move[0] + R_rotate[1][1] * move[1]
            move = [x_move, y_move]
        else: # 아니라면 다시 큐에 저장
            turn.appendleft([time, direction])

print(t)