[백준] [Python] 3190번 뱀 - 큐, Greedy

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

3190번: 뱀

 

 

Hint

1. 뱀을 큐로 표현

2. 뱀이 존재하는 자리를 담을 visit 2차원 리스트

 

 

Python

#https://www.acmicpc.net/problem/3190
import sys
from collections import deque
n = int(sys.stdin.readline())

board = [[-1]*n for _ in range(n)]
for _ in range(int(sys.stdin.readline())):
    x, y = map(int,sys.stdin.readline().split())
    board[x-1][y-1] = "a"

turn = []
for _ in range(int(sys.stdin.readline())):
    t, di = sys.stdin.readline().split()
    turn.append((int(t)-1, di))

# 0=Right, 1=Down, 2=Left, 3=UP 
dx = [0,1,0,-1]
dy = [1,0,-1,0]

q = deque([[0,0,0]]) # x,y, direction
cnt = 0
tIdx = 0

di = 0
while True:
    cnt += 1
    #print(q,cnt)
    nx = q[0][0] + dx[q[0][2]]
    ny = q[0][1] + dy[q[0][2]]
    
    if nx == -1 or nx == n or ny == -1 or ny == n:
        print(cnt)
        break
    if board[nx][ny] !='a' and board[nx][ny] != -1 :
        print(cnt)
        break
    
    if tIdx < len(turn) and cnt-1 == turn[tIdx][0]:
        #print(cnt, di)
        if turn[tIdx][1] == "D":
            di = di+1 if di != 3 else 0
        elif turn[tIdx][1] == "L":
            di = di-1 if di != 0 else 3
        tIdx += 1
        
        
    q.appendleft([nx,ny,di])

     #print(board[nx][ny],nx,ny)
    if board[nx][ny] != "a":
        p = q.pop()
        board[p[0]][p[1]] = -1

    board[nx][ny] = di