[백준] 3190. 뱀/Python - Gold4

❓문제

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

성능 요약

메모리: 114200 KB, 시간: 148 ms

분류

구현, 자료 구조, 시뮬레이션, 덱, 큐

문제 설명

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

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

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

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

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

✍🏻풀이

테스트케이스 3번을 살펴보면 뱀은 위와 같이 움직인다. 13초에 머리를 움직이면 12초일 때 꼬리가 13초일 때 머리가 움직이는 방향에 있으므로 충돌하여 멈추게 된다. 그러므로 게임이 13초에 종료되는 것이다.

방향 따라서 뱀이 움직이려는 다음 칸이 범위에서 벗어나거나 몸통과 만나면 while문을 중단시킨다. 이때 현재 시간+1을 반환한다. 벗어나거나 부딪히지 않는다면 사과가 있는 위치인지 없는 위치인지 확인한다. 사과가 없는 위치라면 꼬리를 큐에서 뺀다. 사과가 있다면 리스트에서 사과를 제거한다. 그리고 뱀의 현재 머리 위치를 큐에 넣고 시간을 +1 한다. 이렇게 시간에 +1을 하다보면 뱀의 방향 전환 시간이 된다. 뱀의 방향 전환 시간에 있는 방향에 따라 머리는 오른쪽과 왼쪽으로 돌리면 된다.

💻코드

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
K = int(input())
apples = [list(map(int, input().split())) for _ in range(K)]
L = int(input())
turns = deque([input().split() for _ in range(L)]) # X초가 끝난 뒤에 뱀이 C 방향으로 90도 회전.
# 방향 전환 D = 오른쪽, L = 왼쪽
rotate = {'D': 1, 'L': -1}
# 북, 동, 남, 서
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]

def OutOfRange(y, x):
    return False if 0 < y <= N and 0 < x <= N else True

def game(y, x, d):
    t = 0
    move = deque([(y, x)])
    while True:
        ny, nx = y + dy[d], x + dx[d]
        if OutOfRange(ny, nx) or (ny, nx) in move: # 범위를 벗어나면 멈춤.
            break

        if [ny, nx] not in apples: # 사과가 없다면 꼬리 제거
            move.popleft()
        else:
            apples.remove([ny, nx])
            
        y, x = ny, nx
        move.append((ny, nx))
        t += 1

        if turns and t == int(turns[0][0]):
            turn = turns.popleft()[1]
            d = (d + rotate[turn]) % 4 # 왼쪽 또는 오른쪽으로 90도 회전.

    return t+1

print(game(1, 1, 1)) # 오른쪽으로 향한다고 하였으므로 방향을 1로 함.

📍후기

문제를 잘못 이해해서 머리랑 몸이 왜 부딪히는 경우가 왜 생기는지 의문이었다. 사과를 먹으면 뱀의 길이가 늘어나기 때문이라는 걸 뒤늦게 알아서 좀 많이 헤맨 문제였다...
다른 사람들의 풀이를 보면 2차원 배열을 만들어서 뱀이 지나가는 것과 사과가 유무를 표시하였는데 굳이 그럴 필요가 없는 문제다. 다만, 오히려 기존 사과가 있는 배열에서 사과를 먹고 지우는 것이 시간이 더 걸릴 수도 있다. 이 부분은 확인하지 못하였으니 궁금하다면 개인적으로 찾아보길...