알고리즘: 백준 3190번 뱀 (feat. python)

 

3190번: 뱀

 

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

N = int(read())
K = int(read())
snake = [[0 for _ in range(N)] for _ in range(N)]
snake[0][0] = -1
apple = [[0 for _ in range(N)] for _ in range(N)]
for i in range(K):
    ay, ax = list(map(int, read().split()))
    apple[ay-1][ax-1] = 1
dir = deque()
L = int(read())
tmp = 0
for _ in range(L):
    n, d = read().split()
    dir.append([int(n)-int(tmp), d])
    tmp = n


def sol():
    eating = deque()
    count = 0
    cx, cy = 0, 0
    go = [[1, 0], [0, 1], [-1, 0],  [0, -1]]
    d = go[0]

    while dir:

        cs, cd = dir.popleft()
        while cs:

            nx = cx + d[0]
            ny = cy + d[1]
            count += 1
            cs -= 1
            if 0 <= ny < N and 0 <= nx <N and snake[ny][nx] != -1:
                snake[ny][nx] = -1
                
                if apple[ny][nx] == 1:
                    apple[ny][nx] = 0
                    snake[cy][cx] = -1
                    eating.append([cy, cx])

                else:
                    snake[cy][cx] = 0
                    
                    if len(eating) != 0:
                        ey, ex = eating.popleft()
                        eating.append([cy, cx])
                        snake[ey][ex] = 0
                        snake[cy][cx] = -1

            else:
                return count

            cx = nx
            cy = ny

        if d == go[0]:
            if cd == 'D':
                d = go[1]
            elif cd == 'L':
                d = go[3]
        elif d == go[1]:
            if cd == 'D':
                d = go[2]
            elif cd == 'L':
                d = go[0]
        elif d == go[2]:
            if cd == 'D':
                d = go[3]
            elif cd == 'L':
                d = go[1]
        elif d == go[3]:
            if cd == 'D':
                d = go[0]
            elif cd == 'L':
                d = go[2]

    else:
        cx += d[0]
        cy += d[1]
        count += 1
 
        while 0 <= cy < N and 0 <= cx <N and snake[cy][cx] != -1:
                cx += d[0]
                cy += d[1]
                count += 1
            
    return count

print(sol())