[백준] 3190번 뱀 - Python

이번에 해결해 볼 문제는 벡준에 있는 뱀이다.

---

문제 설명

1. N x N 크기의 보드 위에서 게임이 진행된다.
2. 이 게임은 뱀이 기어 나와서 기어다니는데, 다음과 같은 규칙을 지켜야 한다.
   • 뱀은 매 초마다 이동한다.
   • 사과를 먹으면 뱀의 길이가 늘어난다.
   • 뱀이 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.
   • 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
   • 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
   • 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다.
3. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1이며 뱀은 처음에 오른쪽을 향한다.

문제 해결 아이디어

• 문제가 굉장히 길어질 수 있을 것으로 예상되는 문제는 정의가 굉장히 중요하다.
  • 게임의 보드판을 board로 정의
    • board = {사과 : -1, 빈칸 : 0, 뱀 : 1}
  • 뱀의 방향 변환 정보를 info로 정의
    • info = [[X, C]]
    • X초가 끝난 뒤에 C방향으로 방향 변환
    • 주어진 X초는 시작했을 때부터 측정한 시간이므로 뱀이 몇 초동안 움직였는지 측정하기 위해 문제에서 주어진 info에 추가적으로 맨 앞과 맨 뒤에 정보를 추가
    • C = {L : 왼쪽, S : 방향 유지, D : 오른쪽}
• 뱀의 위치는 앞과 뒤에서 삽입과 삭제 연산이 일어날 수 밖에 없으므로 Python의 deque()를 사용해 Queue를 구현해야 한다.

문제 해결 코드

import sys
input = sys.stdin.readline
n = int(input())
k = int(input())

# 사과 : -1, 빈칸 : 0, 뱀 : 1
board = [[0] * n for _ in range(n)]
board[0][0] = 1
for _ in range(k):
    r, c = map(int, input().split())
    board[r-1][c-1] = -1

# 방향 변환 정보
# L : 왼쪽, S : 방향 유지, D : 오른쪽
l = int(input())
# 처음 시작과 마지막 정보를 추가
info = [[0,0]] # 처음 위치
for _ in range(l):
    x, c = input().split()
    info.append([int(x), c])
info.append([info[-1][0]+n, 'S']) # 마지막 이동할 거리와 방향 정보

def move(queue, a, dir, t, result):
    """
    queue : 뱀의 위치
    a : board
    dir : 방향
    t : 움직여야 하는 횟수
    result : 시간
    """
    dr, dc = dir
    n = len(a)

    for i in range(1, t+1):
        # 머리 위치
        r, c = queue[-1]
        # 꼬리의 위치 확인
        tail_r, tail_c = queue[0]

        if 0 <= dr+r < n and 0 <= dc+c < n:
            # 빈칸인 경우 뱀의 길이는 유지한 채 한 칸씩 이동
            if a[dr+r][dc+c] == 0:
                a[tail_r][tail_c], a[dr+r][dc+c] = 0, 1
                queue.append((dr+r, dc+c))
                queue.popleft()
            # 사과인 경우 머리만 한칸 이동하면서 총 길이가 1 늘어남
            elif a[dr+r][dc+c] == -1:
                a[dr+r][dc+c] = 1
                queue.append((dr+r, dc+c))
            # 뱀의 몸통인 경우 return
            elif a[dr+r][dc+c] == 1:
                return queue, a, result+i, False
        # 벽에 부딪힌 경우 return
        else:
            return queue, a, result+i, False
    return queue, a, result+t, True


check = True
result = 0
dir = [[-1,0],[0,1],[1,0],[0,-1]]
dir_i = 1 # 시작은 오른쪽 방향으로 이동

from collections import deque

bam = deque([(0,0)]) # 뱀의 위치

for i in range(1, l+2):
    x, c = info[i]
    t = info[i][0]-info[i-1][0] # 이동한 거리 계산
    bam, board, result, check = move(bam, board, dir[dir_i], t, result)
    # 게임이 끝나지 않은 경우 다음 방향을 업데이트
    if check:
        if c == 'D':
            dir_i = (dir_i + 1) % 4
        elif c == 'L':
            dir_i = (dir_i-1 + 4) % 4
        else:
            dir_i = dir_i
    # 게임이 끝난 경우 출력
    else:
        print(result)
        break

간단한 예시