[PS] 백준#3190 / 뱀

알고리즘 문제 풀이

• 링크 : 뱀
• 해결 : solved
• 시간복잡도 : O(n)
• 분류 : 구현, 덱

풀이 과정

1. cnt를 증가시키면서 반복한다.
2. 방향을 바꿔야하면 바꾼다.
3. 현재 방향으로 한 칸 이동한다.
4. 종료 조건이면 break
5. 이동가능한 칸이면 deque에 해당 칸을 appendleft 한다.
   • 사과가 있으면 pop을 하지 않는다. = 꼬리를 옮기지 않는다.
   • 사과가 없으면 pop = 꼬리를 옮긴다.
6. 1~5번을 반복하면서 while문이 종료되면 cnt를 출력한다.

메모

• 뱀이 위치하고 있는 좌표들을 저장하는 자료구조가 deque이다.
• 왼쪽이 머리(=appendleft) 오른쪽이 꼬리(=pop)

소스코드

N = int(input())
A = int(input())
apples = []
for _ in range(A):
    pos = list(map(int, input().split()))
    pos = list(map(lambda x : x-1, pos))
    apples.append(pos)

L = int(input())
shifts = []
for shift in range(L):
    sec, dir = input().split()
    sec = int(sec)
    shifts.append((sec, dir))

board = [[0]*N for _ in range(N)]
for a in apples:
    board[a[0]][a[1]] = 1
D = 1
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
head = (0,0)
cnt = 0

from collections import deque
shifts = deque(shifts)
snake = deque([head])

while True :

    if shifts:
        if cnt == shifts[0][0]:
            sec, dir = shifts.popleft()
            if dir == 'L':
                D -= 1
                if D == -1 :
                    D = 3
            if dir == 'D':
                D += 1
                if D == 4 :
                    D = 0

    nx = head[0] + dx[D]
    ny = head[1] + dy[D]
    cnt += 1

    if nx < 0 or nx >= N or ny < 0 or ny >= N :
        break
    if snake.count((nx, ny)) :
        break

    snake.appendleft((nx, ny))

    if board[nx][ny] == 0 :
        snake.pop()
    if board[nx][ny] == 1 :
        board[nx][ny] = 0
    head = (nx, ny)

print(cnt)