[Python] 백준 3190번 - 뱀

📖 문제

3190번: 뱀

 

🔎 풀이

deque를 이용하면 풀 수 있는 문제입니다. deque는 이중연결리스트로 구현되어 있기 때문에 맨 앞이나 맨 뒤의 원소를 제거하는데 O(1)의 시간이 걸립니다. 뱀이 사과를 먹은 경우 앞에 새로운 좌표를 추가하고, 사과를 먹지 못한 경우 뒤에서 좌표를 제거해주면 됩니다. 나머지 부분은 문제의 조건에 따라 구현하면 됩니다.

 

주의할 점은 사과의 위치가 (1, 1) 부터 시작한다는 점입니다. 문제에서 "맨 위 맨 좌측(1행 1열)에는 사과가 없다." 라고 간접적으로 알려주고 있습니다. 따라서 좌표를 0부터 설정하는 경우, 입력으로 받은 사과의 위치에서 1씩 빼주어야 합니다.

 

💻 코드

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

n = int(input())
board = [[0 for _ in range(n)] for _ in range(n)]
k = int(input())
for _ in range(k):
    y, x = map(int, input().split())
    board[y-1][x-1] = 1  # index 0부터 설정하면 -1씩 해주기

direct = deque()
l = int(input())
for _ in range(l):
    x, c = input().split()
    direct.append((int(x), c))

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

idx = 0
time = 0
snake = deque()  # 뱀의 좌표
snake.append((0, 0))
board[0][0] = -1

while True:
    # 주어진 시간에 뱀 방향 변경
    if direct and direct[0][0] == time:
        _, mark = direct.popleft()
        if mark == 'L':
            idx += 3
        elif mark == 'D':
            idx += 1
        idx %= 4
    
    x, y = snake[0]
    i, j = x + dx[idx], y + dy[idx]
	
    # 게임이 끝나는 조건
    if not (0 <= i < n) or not (0 <= j < n) or board[j][i] == -1:
        break
	
    # 사과가 없을 시, 뱀의 꼬리 제거
    if not board[j][i]:
        end_x, end_y = snake.pop()
        board[end_y][end_x] = 0
	
    # 뱀 머리 이동
    board[j][i] = -1
    snake.appendleft((i, j))
    
    time += 1

print(time + 1)