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

풀이

예시 2번을 그림으로 옮기면 다음과 같습니다 만약 시간이 1초가 지나 뱀이 움직인다면

다음과 같이 꼬리는 그자리에 존재하고 머리만 한칸 이동하게 됩니다.

4초의 시간이 지나면 왼쪽 그림과 같이 뱀은 모든 사과를 먹고 머리만 이동하게 됩니다. 그리고 8초 후 뱀은 머리를 오른쪽으로 돌리기때문에 오른쪽의 그림처럼 나타납니다.

여태까지 꼬리는 머리와 같은 방향으로 이동했습니다. 하지만 머리의 방향이 바뀌면서 꼬리는 자신이 몸통이 존재하는 영역으로 가야하고 머리는 자신의 머리가 위치한 방향으로 나아가야 합니다. 저는 이를 해결하기 위해 머리가 어떤 방향으로 이동했는지를 담는 큐를 만들어 사과를 먹었지 않았을 경우에만 pop하여 머리의 이동정보가 담긴 큐에서 데이터를 받아와 문제를 해결하였습니다.

코드

n = int(input())
k = int(input())
li, rot = [],[]
graph = [[0]*n for _ in range(n)]
for _ in range(k):
    r,c = map(int,input().split())
    graph[r-1][c-1] = 2
l = int(input())
for _ in range(l):
    x,c = input().split()
    rot.append([int(x),c])

from collections import deque
q_tail=deque()

count=0
def snake():
    global count
    di=1
    r,c=0,0
    tail_r,tail_c=0,0
    for i in rot:
        for _ in range(i[0]-count):
            r += dy[di]
            c += dx[di]
            if r < 0 or r >= n or c < 0 or c >= n:
                return count+1
            if graph[r][c]==2:
                graph[r][c]=1
                count+=1
                q_tail.append(di)
            elif graph[r][c]==1:
                return count+1
                break
            else:
                graph[r][c]=1
                q_tail.append(di)
                di_t=q_tail.popleft()
                graph[tail_r][tail_c] = 0
                tail_r += dy[di_t]
                tail_c += dx[di_t]
                count+=1
        
        if i[1]=='D':
            di= (di+1)%4
        else:
            di = (di+3)%4
    while 1:
        r += dy[di]
        c += dx[di]
        if r < 0 or r >= n or c < 0 or c >= n:
            return count+1
        if graph[r][c]==2:
            graph[r][c]=1
            count+=1
            q_tail.append(di)
        elif graph[r][c]==1:
            return count+1
        else:
            graph[r][c]=1
            q_tail.append(di)
            di_t=q_tail.popleft()
            graph[tail_r][tail_c] = 0
            tail_r += dy[di_t]
            tail_c += dx[di_t]
            count+=1

dx=[0,1,0,-1]
dy=[-1,0,1,0]
graph[0][0]=1
print(snake())