(Python) 백준 3190. 뱀

문제

'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

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

먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.
만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

상세보기

• 정직한 구현 문제로, 기초적인 구현을 공부할 때 괜찮은 문제
• 문제에서 요구하는 조건을 하나하나 구현해 나가는 것이 숙제
• 다음 칸을 확인하여 조건에 맞는 이동 하기
• 필드를 굳이 만들 필요는 없음

from sys import stdin; input = stdin.readline
from collections import deque

def tuple_change(t):                                                        # 튜플값 첫번째는 int, 두번째는 str값이기에 변환
    a, b = t.strip().split()
    return (int(a), b,)

dr = [(0,1),(1,0),(0,-1),(-1,0)]
now_d = 0

timer = 0

N = int(input())
apples = [tuple(map(int, input().split())) for _ in range(int(input()))]    # 전체 사과 위치 받기
nxt = [tuple_change(input()) for _ in range(int(input()))]                  # 방향 전환하는 위치 받기
next = deque(nxt)
dummy = deque()
dummy.append((1,1,))
while dummy:
    if next and next[0][0] == timer:                                        # 방향 이동 체크
        now_d += 1 if next[0][1] == 'D' else -1
        next.popleft()
    
    timer += 1
    
    x, y = dummy[-1]
    dx, dy = dr[now_d%4]
    nx, ny = x + dx, y + dy
    if nx < 1 or nx > N or ny < 1 or ny > N or (nx, ny,) in dummy:          # 벽에 부딪히거나 내 몸이면, 끝내기
        break
    
    if (nx,ny,) in apples:                                                  # 사과 먹었는지 판별
        apples.remove((nx,ny,))
        dummy.append((nx,ny,))
    
    else:                                                                   # 사과 없으면, 꼬리 줄이기
        dummy.append((nx,ny,))
        dummy.popleft()

print(timer)

• 방향의 변화를 기초적인 Direction을 만들고, 나머지 연산자를 사용하여 변화시킴
• 뱀의 위치 변화를 계속해서 추적해 나가야 하기 때문에, 큐를 사용하는 게 효율적이라고 생각
• 사과가 최대 100개까지 올 수 있기 때문에 remove를 사용. visited를 사용하여 표시하거나 삭제하거나의 선택지가 있는데, 최대 갯수가 적기 때문에 remove도 괜찮다고 생각했음. visited로도 풀어봤는데, 속도와 메모리에서 큰 차이는 없음.