BOJ - 뱀 3190번 (python)

❓ 문제 - 백준 뱀 3190번 - python 풀이법

출처 

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

3190번: 뱀

 

 

 

📝 문제해결법

1. 이 문제는 Queue + 구현으로 풀었다.

• board를 통해 사과의 위치를 입력 받고, 방향을 변경할 시간과, 움직일 방향을 change 큐에 넣는다 .
• dx, dy로 순서를 우, 하, 좌, 상으로 하여 만약 뱀의 방향을 'L'  로 변경할 땐  dx, dy의 왼쪽 인덱스로 바꿔서 이동하고, 방향을 'R'로 변경할 땐 dx, dy의 오른쪽 인덱스로 바꿔서 이동한다. (=> change_dir 함수)
• 뱀의 길이가 1일땐 뱀의 꼬리와 머리가 같으며, snack란 큐를 사용하여 뱀의 꼬리 x,y와 뱀의 머리x,y 를 큐에 넣어 저장한다.
• 처음 움직이는 방향에 맞춰 머리를 이동시키고 time을 +1 해주며, 머리가 움직인 곳이 벽이거나 자기 자신이라면 return 하여 움직임을 멈춘다.
• 만약 머리를 이동시킨 곳에 사과가 있다면, 몸길이가 길어지므로 해당 board에 뱀을 표시하고 snack큐에 새로운 머리 위치를 append 한다.
• 만약 머리를 이동시킨 곳에 사과가 없다면, 꼬리의 위치를 변경시키기 위해 snack큐에 들어있는 꼬리 위치를 popleft를 통해 제거하고, 꼬리부분을 board에서 뱀의 부분을 빈공간(0)으로 변경한다.
• time 후에 뱀의 방향을 변경시킬 시간이 오면 change_dir 함수를 통해 뱀의 이동방향을 변경한다.

 

💻 소스코드

# 뱀 - BOJ 3190
# Queue + 구현
from collections import deque
n = int(input())
k = int(input())

board = [[0]*n for _ in range(n)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
change = deque()
for i in range(k):
    x, y = map(int, input().split())
    board[x-1][y-1] = 1

time = 0
snack = deque()
snack.append((0, 0))
board[0][0] = 2
dir = 0

for i in range(int(input())):
    x, c = map(str, input().split())
    change.append((int(x), c))

def change_dir(c):
    global dir
    if c == 'L':
        if dir == 0:
            dir = 3
        else:
            dir -= 1
    else:
        if dir == 3:
            dir = 0
        else:
            dir += 1

def solve():
    global time, dir
    time_x, c = change.popleft()
    while True:
        if len(snack) == 1:
            tail_x, tail_y = snack[0]
            head_x, head_y = tail_x, tail_y
        else:
            tail_x, tail_y = snack[0]
            head_x, head_y = snack[-1]
        nx = head_x + dx[dir]
        ny = head_y + dy[dir]
        time += 1
        if nx < 0 or nx > n-1 or ny < 0 or ny > n-1 or board[nx][ny] == 2:
            return
        if board[nx][ny] == 1:
            board[nx][ny] = 2
            snack.append((nx, ny))
        else:
            snack.popleft()
            snack.append((nx, ny))
            board[tail_x][tail_y] = 0
            board[nx][ny] = 2
        if time_x == time:
            change_dir(c)
            if len(change) > 0:
                time_x, c = change.popleft()
    return

solve()
print(time)