이해

• 도스게임에서는 뱀이 N x N 정사각 보드 위에서 기어다닌다. 사과를 먹으면 뱀 길이가 늘어나고, 뱀이 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.
• 게임이 시작할때 뱀은 맨위 맨좌측(1, 1)에 위치하고 처음에 오른쪽을 향하고 뱀의 길이는 1이다.
• 뱀은 매 초마다 다음과 같은 규칙을 따르며 이동한다.
  • 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
  • 이동한 칸에 사과가 있는 경우 그 칸에 있떤 사과가 없어지고 꼬리는 움직이지 않는다.
  • 이동한 칸에 사과가 없는 경우 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다.
• 사과의 위치와 뱀의 이동경로가 주어질 때 게임이 몇 초에 끝나는지 출력하라.

계획

• 자료구조 queue 사용하여 뱀의 몸의 전체 위치를 queue에 넣어준다.
• 몸길이를 늘려 머리를 위치시킬 칸을 구해준 후 칸이 벽이나 자기자신의 몸과 부딪히는 지 체크해준다.
• 부딪히지 않는 경우에는 머리를 위치시킬 칸을 queue에 append해주고 칸에 사과가 있는지 체크해준다.
• 칸에 사과가 없는 경우 queue에서 맨 앞 요소를(꼬리가 위치한 칸) pop해주어 꼬리가 위치한 칸을 비워준다.

실행

from collections import deque

def turn(d, dir):
    if dir == "L":
        return d - 1 if d - 1 >= 0 else 3
    elif dir == "D":
        return d + 1 if d + 1 <= 3 else 0

n = int(input())
k = int(input())

board = [[0]*n for _ in range(n)]

for _ in range(k):
    x, y = map(int, input().split())
    board[x-1][y-1] = 1

pos_queue = deque([(0, 0)])
change_dir = deque()
for _ in range(int(input())):
    x, c = input().split()
    change_dir.append((int(x), c))

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

time = 1
d = 0

while True:
    nx, ny = pos_queue[-1][0] + dx[d], pos_queue[-1][1] + dy[d]
    if not (0 <= nx <= n-1 and 0 <= ny <= n-1 and (nx, ny) not in pos_queue):
        break
    
    # 몸길이를 늘려 머리를 다음칸에 위치시킴
    pos_queue.append((nx, ny))
    # 사과가 있는 경우 사과를 칸에서 제거
    if board[nx][ny] == 1:
        board[nx][ny] = 0
    # 사과가 없는 경우 몸길이를 줄여서 꼬리가 위치한 칸을 비워줌
    else:
        pos_queue.popleft()
    if change_dir and time == change_dir[0][0]:
        d = turn(d, change_dir.popleft()[1])
    time += 1
print(time)

개선

• 딱히 없는 것 같다.

회고

• 쉬웠다.
• 예전에 “이것이 코딩 테스트다” 책을 공부하면서 풀어봤던 문제라서 문제에서 사용할 자료구조를 적절히 선택해서 막힘없이 잘 푼 것 같다.