[BOJ 3190] 뱀 (Python)

문제

뱀

문제 해설

이 문제 역시 시뮬레이션이다. 자료구조 덱을 이용해 뱀이 차지하고 있는 공간을 담아 맵에 처리해 주었고, 시간을 계속 체크해 주어 방향전환이 이뤄져야 하는 시간에 방향 전환만 이뤄지게 해주면 된다. 게임이 정확히 언제 종료되는지 종료조건에 대해서 파악하는 것이 중요하다고 생각한다.

종료조건
1. 뱀의 머리가 맵밖을 벗어남.
2. 뱀의 머리가 자신의 몸통을 통과함.

소스 코드

from collections import deque

deq = deque()
time = 0
convert = deque()  # 방향 전환이 이루어지는 정보
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
d = 1  # 현재 방향
n = int(input())
k = int(input())
graph = [[0] * n for _ in range(n)]

# 사과
for i in range(k):
    a, b = map(int, input().split())
    graph[a - 1][b - 1] = 1

l = int(input())
for i in range(l):
    a, b = map(str, input().split())
    convert.append([int(a), b])

# 방향 전환
def convert_dir(dir):
    global d
    # 오른쪽
    if dir == "D":
        if d == 3:
            return 0
        else:
            return d + 1
    # 왼쪽
    else:
        if d == 0:
            return 3
        else:
            return d - 1


# start
deq.append([0, 0])
graph[0][0] = 2
while True:
    time += 1
    x, y = deq.popleft()
    deq.appendleft([x, y])
    nx = x + dx[d]
    ny = y + dy[d]
    # 맵밖
    if nx < 0 or nx >= n or ny < 0 or ny >= n:
        break
    # 자기 몸에 박는다
    if graph[nx][ny] == 2:
        break
    # 사과가 있다
    if graph[nx][ny] == 1:
        graph[nx][ny] = 2
        deq.appendleft([nx, ny])
    # 사과가 없다
    else:
        graph[nx][ny] = 2
        deq.appendleft([nx, ny])
        a, b = deq.pop()
        graph[a][b] = 0
    # 방향을 돌려야 한다
    if convert and convert[0][0] == time:
        d = convert_dir(convert[0][1])
        convert.popleft()
print(time)