[백준/Python] 3190번 : 뱀

문제

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

3190번: 뱀

풀이

초기 설정
0으로 이루어진 NXN 크기의 graph를 생성한다.
사과가 있는 위치는 1로 변경한다.
방향 변환 정보를 deque으로 저장한다. (li)
x, y 위치 정보를 위해 리스트를 생성하고, 방향을 위한 d를 초기화한다.
뱀의 머리부터 꼬리까지 차지하고 있는 위치를 저장하기 위한 deque를 생성하고 시작 위치를 넣어준다. (dq)

반복
방향 변환 정보가 존재하고 time에 해당한다면 방향을 전환해 준다.

뱀 머리 위치를 이동하고 시간을 증가시킨다. (nx, ny)
뱀의 머리가 graph를 벗어나거나, 자신의 몸에 닿는다면 종료한다. (dq내에 좌표가 존재하면 뱀의 몸이 있는 곳이다)
어니라면 뱀의 머리를 dq에 append한다.

만약 뱀 머리 위치에 사과가 있다면 사과를 없앤다. (꼬리는 움직이지 않는다)
사과가 없다면 dq.popleft로 뱀 꼬리 위치를 제거한다.
*dq가 뱀 전체 몸이며, 오른쪽이 뱀의 머리가 되고 왼쪽이 뱀의 꼬리가 된다.

코드

import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
k = int(input())
graph = [[0]*n for _ in range(n)]
for _ in range(k):
    x, y = map(int, input().split())
    graph[x-1][y-1] = 1

l = int(input())
li = deque([input().rstrip().split() for _ in range(l)])

x = [1, 0, -1, 0]
y = [0, 1, 0, -1]
time, d, nx, ny = 0, 0, 0, 0
dq = deque([(nx, ny)])
while True:
    if li and int(li[0][0]) == time:
        d += (1 if li.popleft()[1] == 'D' else -1)

    nx += x[d % 4]
    ny += y[d % 4]
    time += 1
    if nx < 0 or ny < 0 or nx >= n or ny >= n or (ny, nx) in dq:
        break

    dq.append((ny, nx))
    if graph[ny][nx] == 1:
        graph[ny][nx] = 0
    else:
        dq.popleft()

print(time)