[백준] 3190번: 뱀

문제 링크

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

코드

import sys
from collections import deque

imput = sys.stdin.readline

n = int(input())  # 보드 크기
# 좌측 상단의 좌표가 (1, 1)이므로 보드 크기를 n + 1로 설정한다
board = [[0] * (n + 1) for _ in range(n + 1)]

k = int(input())  # 사과 개수
for _ in range(k):
    y, x = map(int, input().split())  # 사과 좌표
    # 보드의 사과 좌표에 1을 저장한다
    board[y][x] = 1

l = int(input())  # 방향 전환 횟수
dir_change = []  # 방향 전환을 저장할 리스트
for _ in range(l):
    # time은 방향이 바뀌는 시간, dir은 바꿀 방향 (왼쪽, 오른쪽)
    time, dir = input().split()
    time = int(time)
    dir_change.append((time, dir))

# 방향 전환, 순서대로 오른쪽, 아래, 왼쪽, 위
# D면 인덱스 +1, L이면 인덱스 -1
i = 0  # 처음 방향은 오른쪽으로 이동
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]

# 뱀의 몸통을 데크로 관리한다
# 머리가 이동할 때는 appendleft로 왼쪽으로 넣어주고 꼬리가 줄어들 때는 pop으로 오른쪽을 뺀다
# 만약 새로 이동한 곳에 사과가 있다면 (값이 1이라면) 값을 0으로 바꾸고
# pop을 수행하지 않고 appendleft만 해준다 (뱀 길이가 늘어난다)
snake = deque()

# 뱀의 머리가 몸통에 닿는지 검사하기 위해 set자료형에 뱀이 있는 좌표를 넣어준다
# 이동할때 데크와 같이 remove, add 해주면서 관리한다.
overlap_check = set()

# 시작 좌표 (1, 1)
# y, x는 뱀 머리의 현재 좌표
y = x = 1
snake.appendleft((y, x))
overlap_check.add((y, x))

# 몇 초 동안 살아있는지 기록
count = 0

# 몸통이나 벽에 닿으면 count를 출력하고 동료
# 닿지 않는 경우 snake와 overlap_check에 값을 저장한다
while True:
    # 우선 count를 증가시키고 머리가 이동할 좌표를 구한다
    count += 1
    ny = y + dy[i]
    nx = x + dx[i]

    # 몸통에 닿는지 또는 벽에 닿는지 확인
    if (ny, nx) in overlap_check \
            or ny <= 0 or ny > n \
            or nx <= 0 or nx > n:
        print(count)
        break

    # 사과가 있는지 확인
    if board[ny][nx] == 1:
        board[ny][nx] = 0  # 사과를 없앤다
    else:
        # 사과를 못 먹었으므로 꼬리를 이동시킨다
        tail = snake.pop()
        overlap_check.remove(tail)
    # 머리를 이동시킨다
    snake.appendleft((ny, nx))
    overlap_check.add((ny, nx))
    y, x = ny, nx

    # 방향을 바꿀 지 확인한다
    if dir_change and count == dir_change[0][0]:
        _, cmd = dir_change.pop(0)
        if cmd == "L":  # 왼쪽으로 방향 전환
            i = (i - 1) % 4
        else:  # 오른쪽으로 방향 전환
            i = (i + 1) % 4