[Baekjoon] 3190: 뱀

문제

어릴 때 많이 했던 뱀 게임을 구현하는 문제이다.

 

풀이

내 풀이

import sys
from collections import deque

n = int(sys.stdin.readline())
apple_count = int(sys.stdin.readline())

board = [[0 for i in range(n)] for i in range(n)]
board[0][0] = 1

for i in range(apple_count):
    r, c = map(int, sys.stdin.readline().split())
    board[r-1][c-1] = 2

directs = deque([])
for i in range(int(sys.stdin.readline())):
    s, d = sys.stdin.readline().split()
    directs.append([int(s), d])
    
x = 0
direct = [[0, 1], [1, 0], [0, -1], [-1, 0]]
cur_direct = 0
head = [0, 0]
tail = [0, 0]
snake = deque([[0, 0]])
while True:
    if len(directs) > 0 and directs[0][0] == x:
        s, d = directs.popleft()
        if d == 'D':
            cur_direct = (cur_direct + 1) % 4
        else:
            cur_direct = (cur_direct - 1) % 4
    
    snake.append([snake[-1][0]+direct[cur_direct][0], snake[-1][1]+direct[cur_direct][1]])
    
    if snake[-1][0] < 0 or snake[-1][0] >= n or snake[-1][1] < 0 or snake[-1][1] >= n:
        break
    
    if board[snake[-1][0]][snake[-1][1]] == 1:
        break
    
    if board[snake[-1][0]][snake[-1][1]] == 2:
        board[snake[-1][0]][snake[-1][1]] = 1
    else:
        board[snake[-1][0]][snake[-1][1]] = 1
        board[snake[0][0]][snake[0][1]] = 0
        snake.popleft()
    x += 1

print(x+1)

board 리스트를 선언하여 빈곳은 0 뱀은 1 사과는 2로 체크하여 구현하였다.

뱀의 몸통을 다 체크하는 것은 비효율적이기에 머리와 꼬리만 체크하여 구현했다.

 

처음에 머리와 꼬리 인덱스를 수시로 바꿔주는 것으로 구현했지만 꼬리의 위치가 바뀌는 것이 문제가 되었다.

예를 들어, 뱀이 똬리모양으로 말려 있으면 상하좌우 다 뱀의 몸에 해당하기 때문에 그 다음 꼬리가 어디인지 모르게 되기 때문이다.

 

때문에, 머리와 꼬리만 체크를 하되 몸통의 순서를 알 수 있도록 deque을 사용하여 0번째 인덱스는 꼬리 마지막 인덱스는 머리로 하여 이동할 시 끝 인덱스(머리)에 새로운 위치를 추가하고, 사과를 안먹었을 시 처음 인덱스(꼬리)가 삭제되어 다음 몸통이 꼬리가 될 수 있도록 하였다.

 

회고

뱀의 길이와 보드 크기가 매우 커지면 공간 복잡도가 매우 커질 것 같다.

통과는 되었지만 이번 문제는 한 번 더 고민해보고 구현 문제를 앞으로 더 접해봐야 될 것 같다.