[백준] 3190 뱀 (Python 파이썬)

from collections import *

n = int(input())
board = [[0] * n for _ in range(n)]
k = int(input())

for i in range(k):
    x,y = map(int,input().split())
    board[x-1][y-1] = -1
board[0][0] = 0

l = int(input())
move = defaultdict()

for i in range(l):
    sec, dir = input().split()
    move[sec] =dir

dy = [0,0,1,-1]
dx = [1,-1,0,0]

Q= deque()
sec = 0
dir = "right"
Q.append((0, 0))

while True:
    x,y = Q.pop()
    Q.append((x,y))
    # 방향전환 하는 경우
    if str(sec) in move:
    	# 진행방향이 오른쪽인 상태에서 오른쪽회전하면 아래로이동 왼쪽회전이면 위로이동
        if dir=="right":
            if move[str(sec)]=='L':
                ny = y+dy[1]
                nx = x+dx[1]
                dir = "up"
            else:
                ny = y+dy[0]
                nx = x+dx[0]
                dir = "down"
        # 진행방향이 왼쪽인 상태에서 오른쪽회전하면 위로이동 왼쪽회전이면 아래로이동
        elif dir=="left":
            if move[str(sec)]=='L':
                ny = y+dy[0]
                nx = x+dx[0]
                dir = "down"
            else:
                ny = y+dy[1]
                nx = x+dx[1]
                dir = "up"
        # 진행방향이 위인 상태에서 오른쪽회전하면 오른쪽이동 왼쪽회전이면 왼쪽이동
        elif dir=="up":
                if move[str(sec)] == 'L':
                    ny = y+dy[3]
                    nx = x+dx[3]
                    dir = "left"
                else:
                    ny = y+dy[2]
                    nx = x+dx[2]
                    dir = "right"
        # 진행방향이 아래인 상태에서 오른쪽회전하면 왼쪽이동 왼쪽회전이면 오른쪽이동
        else:
            if move[str(sec)] == 'L':
                ny = y+dy[2]
                nx = x+dx[2]
                dir = "right"
            else:
                ny = y+dy[3]
                nx = x+dx[3]
                dir = "left"
		# 새로운 이동이 보드를 나가지 않고 몸통에 부딪히지 않는 경우
        if 0<=ny<n and 0<=nx<n and (nx,ny) not in Q:
        	# 사과 먹을떄 Q에 헤드 추가(몸통길이 증가)
            if board[nx][ny] == -1:
                board[nx][ny] = sec+1
                Q.append((nx,ny))
            # 사과 안먹을떄 Q에 헤드추가하고 꼬리 삭제(몸통길이 증가X)
            else:
                board[nx][ny] = sec+1
                Q.append((nx, ny))
                Q.popleft()
        # 새로운 이동이 보드나 몸통에 부딪히는 경우
        else:
            break
	# 방향 전환 X
    else:    
    	# 원래 이동방향으로 한칸씩 이동
        if dir == "right": 
            ny = y + dy[2]
            nx = x + dx[2]    
        elif dir == "left":   
            ny = y + dy[3]
            nx = x + dx[3]    
        elif dir == "up":   
            ny = y + dy[1]
            nx = x + dx[1]   
        else:
            ny = y + dy[0]
            nx = x + dx[0]
        # 새로운 이동이 보드를 나가지 않고 몸통에 부딪히지 않는 경우
        if 0 <= ny < n and 0 <= nx < n and (nx, ny) not in Q:
        	# 사과 먹을떄 Q에 헤드 추가(몸통길이 증가)
            if board[nx][ny] == -1:
                board[nx][ny] = sec+1
                Q.append((nx, ny))
            # 사과 안먹을떄 Q에 헤드추가하고 꼬리 삭제(몸통길이 증가X)
            else:
                board[nx][ny] = sec+1
                Q.append((nx, ny))
                Q.popleft()
        # 새로운 이동이 보드나 몸통에 부딪히는 경우
        else:
            break
    sec+=1

print(sec+1)