뱀

알고리즘 구분 : 구현

문제 풀이 : 해당 문제는 'Dummy'라는 도스 게임과 유사한 형태로, 종료 규칙은 뱀이 이리저리 기어 다니다가 벽 또는 자기 자신의 몸과 부딪히는 경우이며, 이동 규칙은 이러합니다.
1. 뱀이 몸길이를 늘려 머리를 다음 칸에 위치시킨다.
2. 만약 이동한 칸에 사과가 있다면, 이동한 칸에 있던 사과가 없어지고 꼬리는 움직이지 않음.
3. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여 꼬리가 위치하 던 칸을 비워주며, 전체 몸길이는 변하지 않음
구현하는 과정에서 뱀이 이동할 때, 뱀의 위치를 큐로 저장해야 겠다는 판단을 했습니다. 꼬리를 빼낸다는 것은 선입 선출의 구조와 유사하고, 사과를 먹는 행위는 큐에서 append()를 하는 행위와 유사하기 때문입니다.
또한 방향 변환 정보 역시 문제에서 시간이 증가하는 순으로 주어진다는 점에서 착안하여, 반복문으로 같은 시간이 있는지 리스트에서 확인하는 방식이 아닌 큐로 구현하여, 큐의 맨 앞부분에 저장되어 있는 시간과 동일한 시간일 경우, 해당 값을 활용한 이후에 popleft() 시키는 방식을 활용하였습니다.

소스 코드 :

from collections import deque

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

# 뱀이 움직일 좌표
graph = [[0] * (n + 1) for _ in range(n + 1)]

# 사과 위치 표현
for _ in range(k):
    a, b = map(int, input().split())
    graph[a][b] = 1

# 동, 남, 서, 북 순서 왼쪽이면 -1, 오른쪽이면 +1해서 인덱스 변환으로 방향 조절
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
now_direction = 0


# 방향 전환 함수
def change_diretion(change):
    global now_direction

    if change == 'L':
        now_direction -= 1
        if now_direction < 0:
            now_direction = 3
    elif change == 'D':
        now_direction += 1
        if now_direction > 3:
            now_direction = 0


# 방향 변환 변수, 시간당 방향 변환 정보 입력
time_index = 0
time_data = []
l = int(input())
for _ in range(l):
    time_data.append(list(map(str, input().split())))

# 현재시간, 뱀의 좌표, 덱 리스트 변환용 변수, 탈출용 boolean 변수, 사과 여부 변수
time = 0
snake = deque([[1, 1]])
temp = []

# 게임 끝나는지 여부 체크 함수
def check(nx, ny, temp, length):
    global n
    escape = 0
    if nx < 1 or nx > n or ny < 1 or ny > n:
        escape = 1
    if length > 1:
        for i in range(length - 1):
            if nx == temp[i][0] and ny == temp[i][1]:
                escape = 2
    return escape


while True:
    # deque 리스트 변환, 뱀의 머리 부분 좌표 설정(x, y)
    temp = list(snake)
    x, y = temp[-1][0], temp[-1][1]

    # 시간 증가
    time += 1

    # 뱀의 이동 규칙 적용
    nx = x + dx[now_direction]
    ny = y + dy[now_direction]
    if check(nx, ny, temp, len(snake)):
        break
    snake.append([nx, ny])

    if 1 <= nx and nx <= n:
        if 1 <= ny and ny <= n:
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
            else:
                snake.popleft()


    # 방향 변환
    if time_index < l:
        if time == int(time_data[time_index][0]):
            change_diretion(time_data[time_index][1])
            time_index += 1

print(time)

• 문제 출처 : https://www.acmicpc.net/problem/3190
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.