백준: 3190 뱀

문제

3190번: 뱀

 

문제 풀이

 NxN 정사각 보드가 있을 때, 초기의 뱀의 길이는 1이고 뱀은 처음에 오른쪽을 향한다. 이때 뱀은 사과를 먹게 되면 몸의 길이가 1 증가하고, 아닌 경우는 길이가 그대로 유지되고 이동한다. 또한 특정 시간 초 후에 전환하는 방향 'L', 'D'가 주어지는데 L인 경우 왼쪽, D인 경우 오른쪽으로 90도 회전한다. 이와 같은 조건에 따라 뱀 게임을 몇 초 동안 수행할 수 있는지 반환하여야 한다.

 

 문제는 BFS를 통해 다음과 같이 탐색하면 된다.

• 뱀은 오른쪽을 향하므로 (0, 0)에서 (0, 1)을 더하가며 탐색을 진행한다.
• 특정 시간 초가 되면, 'L', 'D'에 따라 전환할 방향을 선택하고 그 방향으로 탐색을 진행한다.
• 뱀의 꼬리를 다시 만나거나, NxN 정사각 보드 밖으로 나갈 경우 게임이 중단 된다.

 

코드

from sys import stdin
from collections import deque


def change_dir(cur_dir, change):
    return (cur_dir - 1 if change == 'L' else cur_dir + 1) % 4


def visitable(x, y):
    return 0 <= x < n and 0 <= y < n and graph[x][y] != SNAKE


def bfs(start):
    q = deque([start])
    time = 0
    cur_dir = 0
    x, y = 0, 0
    graph[x][y] = SNAKE

    while True:
        if move and move[-1][0] == time:
            cur_dir = change_dir(cur_dir, move.pop()[1])

        next_x, next_y = x + dirs[cur_dir][0], y + dirs[cur_dir][1]

        time += 1

        if visitable(next_x, next_y):
            if graph[next_x][next_y] == APPLE:
                graph[next_x][next_y] = SNAKE
                q.append((next_x, next_y))
            elif graph[next_x][next_y] == EMPTY:
                graph[next_x][next_y] = SNAKE
                q.append((next_x, next_y))
                tail_x, tail_y = q.popleft()
                graph[tail_x][tail_y] = EMPTY
            x, y = next_x, next_y
        else:
            break
    return time


if __name__ == '__main__':
    EMPTY, SNAKE, APPLE = 0, 1, 2
    n = int(stdin.readline())
    graph = [[0] * n for _ in range(n)]
    dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    move = []

    for _ in range(int(stdin.readline())):
        i, j = map(int, stdin.readline().split())
        graph[i - 1][j - 1] = APPLE

    for _ in range(int(stdin.readline())):
        move_time, move_dir = stdin.readline().split()
        move.append([int(move_time), move_dir])

    move = move[::-1]

    print(bfs([0, 0]))

 `deque`를 활용하여 뱀의 길이를 유지하면서 탐색을 진행한다. 사과를 먹지 못할 경우 뱀의 크기를 줄이고 (`q.popleft`), 사과를 먹을 경우 뱀의 크기를 늘린다. 또한, 뱀의 머리가 꼬리를 밟는 경우를 확인하기 위해, 보드의 값을 뱀으로 수정하여 확인하면 쉽게 해결할 수 있다.😉