3019. 뱀

사용한 자료구조 / 알고리즘

1. 덱(deque)

접근 방법

고전 게임 '스네이크'를 직접 구현하는 알고리즘 문제다.

구현해야 하는 요소는 다음과 같다

1. 사과를 먹을 때마다 뱀의 길이가 증가.
2. 뱀이 자신을 물거나 벽에 닿으면 종료.
3. 뱀이 성공적으로 이동할 경우, 뱀 꼬리를 옮겨줌.
4. 시간에 따른 이동방향 변경

구현한 방법

1. 뱀의 길이: 1로 시작해서 사과를 만날 때마다 증가하는 int 변수.
2. 뱀의 좌표: deque로 관리. len(deque)가 뱀의 길이보다 클 경우, popleft 후 지도에서 뱀을 지워야 한다. (가장 먼저 들어갔던 곳 == 발자취 == 꼬리)
3. 시간 값을 key로 하는 dictionary 를 선언. 매 초마다 value가 있는지 확인한다. 

느낀점, 특이사항

문제를 꼼꼼하게 읽어야 한다. '뱀의 움직임'을 어떻게 구현할 것인가가 명확하게 나와있다. 이런 요소들을 명확하게 파악한 후 문제를 푼다면 시행착오를 많이 줄일 수 있을 것이다. 

1. X초가 지나고 방향을 전환한다.
2. 뱀의 머리가 늘어나서 한 칸 전진 후 꼬리에서 한 칸 줄어든다.

pprint 모듈을 import한 후 좌표평면을 보면서 푸는 방법도 괜찮았다. 

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

# 0 우, 1 상, 2 좌, 3 하
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]


# 1. 입력


# 1-1. 좌표평면 설정 뱀 초기값 설정
N = int(input()) # 지도의 크기 입력
sq_lst = [[0]*N for _ in range(N)] # 2차원 좌표평면 선언
sq_lst[0][0] = 1 # 뱀 표시

# 4: 사과
# 1: 뱀

# 1-2. 사과 위치 입력
K = int(input()) # 사과의 갯수
for i in range(K):
    y, x = map(int, input().split())
    sq_lst[y-1][x-1] = 4 # 사과를 '4'로 표시


# 1-3. 명령 입력.
L = int(input()) # 명령의 갯수
direction_dict = dict() # dict 형태로 선언.
for i in range(L): # 명령의 갯수에 따라
    sec, direction = map(str, input().split())
    direction_dict[int(sec)] = direction # 초 - 명령을 딕셔너리 형태로 삽입.


# 2. 선언

d = 0 # 방향 초기값
sec = 0 # '게임 플레이 한 시간' 초기값
snake_Q = deque() # 뱀의 좌표
snake_Q.append([0, 0]) # 큐에 뱀 좌표 초기값 입력
snake_len = 1 # 뱀의 길이. 초기값 == 1

# 3. 연산

while True:

    # 3-1. 스네이크의 움직임 확인

    sec += 1 # 1초 가산.
    y, x = snake_Q[-1] # 마지막 값(머리) 확인

    nx = x + dx[d] # 다음에 갈 예정인 곳의 x좌표
    ny = y + dy[d] # ''' y좌표


    # 3-2. 스네이크가 움직임

    if nx >= N or nx < 0 or ny >= N or\
            ny < 0 or sq_lst[ny][nx] == 1: # 벽에 부딪히거나 꼬리를 물 때

        break # 함수를 종료.

    if sq_lst[ny][nx] == 4: # 4과를 먹었을 때
        snake_len += 1 # 스네이크 길이 1 증가

    sq_lst[ny][nx] = 1 # 사과를 먹거나 말거나 상관 없이
    snake_Q.append([ny, nx]) # Q에 좌표 넣기

    # 3-3. 움직임을 끝낸 스네이크가 꼬리를 끌고 감
    while len(snake_Q) != snake_len:
        tail_y, tail_x = snake_Q.popleft()
        sq_lst[tail_y][tail_x] = 0


    # 3-4 방향전환이 있을 경우 방향 전환.
    if direction_dict.get(sec) == 'L':
        d += 1
        if d == 4:
            d = 0

    elif direction_dict.get(sec) == 'D':
        d -= 1
        if d == -1:
            d = 3


print(sec) # 출력