[백준] 뱀

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

3190번: 뱀

문제

NxN 정사각 보드위에서 진행 되고, 몇몇 칸에는 사과가 놓여져 있다.

보드의 상하좌우 끝에는 벽이 있고, 게임이 시작할 때는 뱀은 맨 위 맨 좌측에 위치하고 뱀의 길이는 1이다.

뱀은 처음에 오른쪽을 향한다.

뱀은 매초 이동하는데 다음과 같은 규칙을 따른다

• 먼저 뱀은 몸 길이를 늘려 머리를 다음 칸으로 위치시킴
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않음
• 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워줌. 몸길이는 변하지 않다는 것이다.

입력조건

• 첫째 줄에 보드의 크기 N이 주어짐(2<=N<=100) 다음 줄에 사과의 개수 K 가 주어짐(0<=K<=100)
• 다음 K개의 줄에는 사과의 위치가 주어지는데, 첫번째 정수는 행, 두번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측(1행 1열)에는 사과가 없다.
• 다음 줄에는 뱀의 방향 변환 횟수 L이 주어짐(1<=L<=100)
• L개의 줄에는 뱀의 방향 변환 정보가 주어지는데, 정수 X와 문자 C로 이루어져 있으며 게임 시작 시간으로부터 X초가 끝난 뒤 왼쪽 또는 오른쪽으로 90도 방향을 회전시킨다는 뜻 

해결 방법

구현 문제이다!

풀다가 유의깊게 봐야할 부분은 맨 위 맨 왼쪽을 1행 1열로 본다는 것과 방향을 바꿀떄는 주어진 시간이 끝난 뒤 방향이 바뀐다는 것을 조심해야한다.

난 이것 떄문에 시간을 엄청 잡아먹었다 ㅎㅎ

뱀이 움직이는 로직대로 그대로 구현하면 된다.

나같은 경우는 뱀에 해당하는 좌표를 큐 리스트에 삽입하여 머리 추가 꼬리 삭제를 하도록 구현하였다.

 

from collections import deque

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

#뱀에 해당하는 좌표 1로 설정 시작은 0,0에서 시작함
graph[0][0]=1
#뱀에 해당하는 좌표 큐에 넣어주기
snake=deque([[0,0]])

#사과가 있는 곳 값 2로 설정
apple_cnt=int(input())
for _ in range(apple_cnt) :
     row, col=map(int, input().split())
     #1행1열이 (0,0)인 것처럼 -1한 인덱스에 넣어주는 것 유의
     graph[row-1][col-1]=2

d=int(input())

#시간과 방향 저장할 리스트 설정
dlist=[]
for _ in range(d) :
    t,order=input().split()
    dlist.append([int(t), order])
#초기준으로 정렬
dlist=sorted(dlist, key=lambda x : x[0])
dlist=deque(dlist)
#시작 시간과 시작 좌표 초기화
time=0
x=0
y=0

#상하좌우로 방향 바꿀 값 저장하는 리스트 설정
nd=[[0,1],[1,0],[0,-1],[-1,0]]

#초기는 오른쪽으로 움직임
direct=0

while True :
    time+=1
    
    #현재 시간의 방향대로 x와 y 좌표 이동
    nx=nd[direct][0]
    ny=nd[direct][1]

    x=x+nx
    y=y+ny
    #x와 y가 범위를 벗어날 때, 해당 위치가 뱀일때
    if x<0 or y<0 or x>n-1 or y>n-1  or graph[x][y]==1:
        break
    #사과를 만났을 때
    if graph[x][y]==2 :
        graph[x][y]=1
        snake.append([x,y])
    #사과도 벽도 뱀도 아닐떄 
    elif graph[x][y]==0 :
    	#꼬리 자르기
        sx, sy=snake.popleft()
        graph[sx][sy]=0
        #해당 좌표 뱀으로 설정
        graph[x][y]=1
        snake.append([x,y])
    #아직 처리하지 못한 방향 전환 명령이 있을 때
    if dlist:
        if time in dlist[0] :
            t, o=dlist.popleft()
            #오른쪽으로 회전
            if o=="D":
                direct+=1
            #왼쪽으로 회전
            elif o=="L" :
                direct-=1
    #dlist의 범위를 넘어서면 director 0으로 초기화
    if direct>=4 or direct<=-4 :
        direct=0

print(time)