백준 3190번 - 뱀 [Python]

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

3190번: 뱀

문제

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

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

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

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

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

문제 유형 / 난이도

구현 / 골드 4

문제 풀이

뱀은 정해진 시간에 L 또는 D 방향으로 90도로 회전하기 때문에 뱀이 사과를 먹지 않을 경우 꼬리를 제거하는 부분을 구현하는 것이 문제이다. 이 부분을 deque를 활용해 앞과 뒤에서 추가하고 뺄 수 있게 만들어 deque의 앞 부분을 꼬리 뒷 부분을 머리로해서 구현하였다. 이렇게 함으로써 회전에 영향을 받지 않고 deque의 앞부분을 빼주기만 하면 꼬리를 제거할 수 있다. 나머지는 문제에 제시된 규칙을 따라 구현하기만 하면된다.

Python

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

def turn(i, d):
    if d == 'L':
        i = (i+1)%4
    if d == 'D':
        i = (i-1)%4
    
    return i

def move():
    x, y = 1, 1
    i = 0
    cnt = 0
    snake = deque([(1, 1)])
    while True:
        x += dx[i]
        y += dy[i]
        cnt += 1
        
        if x <= 0 or x > n or y <= 0 or y > n: break
        if (x, y) in snake: break
        
        snake.append((x, y))
        
        if graph[x][y] == 1:
            graph[x][y] = 0 
            
        else:
            snake.popleft()
        
        if cnt in dir:
            i = turn(i, dir[cnt])
    
    return cnt
         
n = int(input())
k = int(input())

graph = [[0]*(n+1) for _ in range(n+1)]

for _ in range(k):
    x, y = map(int, input().split())
    graph[x][y] = 1

l = int(input())

dir = dict()
for _ in range(l):
    x, c = map(str, input().split())
    dir[int(x)] = c

# right, up, left, down
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

print(move())

feedback

뱀이 있는 위치를 deque로 표현하는게 관건인 문제였다. 해당 아이디어를 기억하자.