문제 링크

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

문제 설명

• 사과의 위치, 방향 전환 시점이 주어짐
• 뱀은 이동할 때 머리 한 칸 전진 후, 꼬리 한 칸 전진
• 사과를 만나면 길이 늘어남 (꼬리 전진 X)
• 벽이나 몸통을 만나는 시점 return

풀이

• 초가 10000 이하로 주어져서 초 단위로 구현
• 머리와 꼬리를 저장하기 위해 deque, 방문 확인을 위해 set 사용
• 사과를 만나면 머리 append, add
• 빈칸을 만나면 머리 apepnd, add, 꼬리 popleft, remove

코드

from collections import deque
import sys


def init():
    ipt = sys.stdin.readline
    n = int(ipt())
    k = int(ipt())
    apples = [list(map(int, ipt().split())) for _ in range(k)]
    board = [[0] * n for _ in range(n)]
    for y, x in apples:
        board[y-1][x-1] = 1
    l = int(ipt())
    commands = [''] * 10001
    for _ in range(l):
        t, d = ipt().split()
        commands[int(t)] = d
    return n, board, commands


def get_time():
    body_q = deque([(0, 0, 'R')])
    body_set = set([(0, 0)])
    for t in range(10001):
        ny, nx, nd = get_next(body_q[-1], commands[t])
        if not (0 <= ny < n and 0 <= nx < n) or (ny, nx) in body_set:
            return t + 1
        # 전진
        body_q.append((ny, nx, nd))
        body_set.add((ny, nx))
        # 빈칸일 때
        if board[ny][nx] == 0:
            ty, tx, td = body_q.popleft()
            body_set.remove((ty, tx))
        # 사과일 때
        elif board[ny][nx] == 1:
            board[ny][nx] = 0


def get_next(head, d):
    cy, cx, cd = head
    nd = cd
    if d:
        nd = get_nd(cd, d)
    if nd == 'R':
        return cy, cx+1, nd
    elif nd == 'L':
        return cy, cx-1, nd
    elif nd == 'U':
        return cy-1, cx, nd
    elif nd == 'D':
        return cy+1, cx, nd


def get_nd(cd, d):
    if cd == 'R':
        if d == 'D':
            return 'D'
        elif d == 'L':
            return 'U'
    elif cd == 'L':
        if d == 'D':
            return 'U'
        elif d == 'L':
            return 'D'
    elif cd == 'U':
        if d == 'D':
            return 'R'
        elif d == 'L':
            return 'L'
    elif cd == 'D':
        if d == 'D':
            return 'L'
        elif d == 'L':
            return 'R'


n, board, commands = init()
print(get_time())