[BOJ 3190] 뱀 (Python3)

www.acmicpc.net/problem/3190

3190번: 뱀

 

N=int(input())
K=int(input())
apples=[]
changes={}
second=0
positions={(0,1):((-1,0),(1,0)), (1,0):((0,1),(0,-1)),(0,-1):((1,0),(-1,0)),(-1,0):((0,-1),(0,1))}
dx,dy=0,1
body=[(1,1)]
 
for i in range(K):
    apples.append(tuple(map(int, input().split())))
 
L=int(input())
for i in range(L):
    X, C=input().split()
    changes[int(X)]=C
 
while True:
    second+=1
    x,y=body[-1]  ##x,y가 머리
    isApple=False
    x, y=x+dx, y+dy
 
    if x<1 or x>N or y<1 or y>N:
        break
    if (x,y) in body:
        break
 
    for ax, ay in apples:
        if x==ax and y==ay:
            isApple=True
            apples.remove((ax,ay))
 
    if isApple==False:
        body.pop(0)
    body.append((x,y))
 
    if second in changes.keys():
        if changes[second]=='L':
            dx, dy=positions[(dx,dy)][0]
        elif changes[second]=='D':
            dx, dy=positions[(dx,dy)][1]
 
print(second)

많이 겁먹었던 문제.

 

시뮬레이션+덱+큐를 이용하는 문제였다.

내가 사용했던 방법은 이렇다.

 

body 안에 있는 값들이 현재 뱀이 위치한 곳들이다. 

 

움직이는 방향을 dx, dy로 설정한다.

그리고 위치를 이전 위치 x,y+dx,dy 하여 구한다. 이때 이전 위치는 리스트(body)에서 제일 마지막 원소를 빼면된다.

이때 이 위치가 영역을 넘어서거나, 이전 몸과 부딪혔다면 break 걸어주고 해당 second 를 리턴한다.

 

현재 위치가 apple 이 있는지 체크한 후, 사과가 있다면 꼬리 부분은 떼주지 않고 머리 부분만 body 배열에 붙인다.

사과가 없다면 리스트 body의 맨 첫번째 원소를 빼준 후 마찬가지로 머리 부분만 body 배열에 붙인다.

 

이때 해당 초가 머리 방향을 바꾸는 시간이라면, dx, dy를 하드 코딩한(..) positions 에 맞게 변환해주면 된다.

collections의 deque를 사용했더라면 더 가독성이 좋았을 것 같다.

애초에 사용하는 것이 맨 왼쪽 원소를 빼는 연산(q.popleft()), 맨 오른쪽 원소를 보거나 붙이는 연산(q.append())이니 말이다.

 

다른 분들(rebas.kr/785) 코드 보니깐 배열 a를 따로 만들어서 뱀의 해당 위치 존재 여부를 체크해주었다.

뱀의 꼬리, 머리에 대한 계산을 할때는 deque인 q에 있는 값을 popleft(), append() 해서 해주었다.

 

나와 다른 점은 뱀의 해당 위치 존재 여부를 body 배열에 넣어 같이 체크했다는 점. 즉 위 분의 코드에서 q+a를 합친 버전으로 했다.