[백준] 3190 - 뱀(파이썬, Python)

출처: https://www.acmicpc.net

www.acmicpc.net/problem/3190

3190번: 뱀

해당 문제는 뱀 머리의 위치를 이동시키며 뱀의 머리가 자신의 몸 또는 벽에 부딪힐 때까지의 시간을 계산하는 것이 목적입니다.

 

접근법 1

종료 조건에 맞게 게임 중단시키기

 

게임의 종료 조건은 두 가지가 있습니다.

1. 뱀의 머리가 벽에 부딪혔을 때 종료됩니다.

2. 뱀의 머리가 자신의 몸에 부딪혔을 때 종료됩니다.

 

저는 위의 조건을 간단히 확인하기 위해 아래와 같은 전략을 세웠습니다.

1. 벽과 뱀의 몸 위치에는 -1을 저장을 하여 뱀의 다음 위치에 -1이 있다면 종료한다.

2. 보드의 상하좌우 끝에 있는 벽을 구현하기 위해 보드판의 크기를 (N+2) X (N+2)로 정하고 첫 행, 끝 행, 첫 열, 끝 열에는 모두 -1을 저장한다

 

전략에 따라 보드판을 그리면 아래와 같습니다.

0 = 빈칸, -1 = 벽을 의미합니다.

 

접근법 2

뱀의 몸길이 관리하기

 

뱀의 이동은 먼저 머리가 움직이고 해당 위치에 사과의 존재 여부에 따라 몸의 상태가 달라지게 됩니다.

 

1. 머리가 움직인 곳에 사과가 있을 경우

- 뱀의 길이가 1 증가합니다.

=> 뱀의 몸 상태를 저장하는 자료구조에 새로 이동한 뱀의 머리 위치만 새로 추가하면 됩니다.

 

2. 머리가 움직인 곳에 사과가 없을 경우 

- 뱀의 몸 길이에는 변화가 없습니다.

=> 뱀의 몸 상태를 저장하는 자료구조에 새로 이동한 뱀의 머리 위치를 추가하고 현재 꼬리 위치는 제거합니다.

 

위의 조건을 보면 자료구조의 Head와 Tail에서 데이터 추가, 삭제가 발생합니다. 따라서 뱀의 몸 상태를 저장하는 자료구조로는 deque를 이용했습니다.

 

접근법 3

회전 방향 결정하기

 

뱀은 입력된 시간에 입력된 방향으로 회전을 합니다.

회전 방향은 뱀의 진행 방향을 기준으로 왼쪽 또는 오른쪽 두 가지만 존재합니다.

 

뱀의 진행 방향과 회전 방향은 아래와 같이 구현했습니다.

dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]

 # 현재 방향 index: (회전 방향이 L일 경우 다음에 향할 방향, 회전 방향이 D일 경우 다음에 향할 방향)
direction = {
    0: (3, 1),
    1: (0, 2),
    2: (1, 3),
    3: (2, 0)
}

※ 회전 방향을 결정하는 규칙은 존재합니다! 저는 문제를 풀 당시 규칙을 찾지 못해 Dictionary에 회전 방향을 저장하는 방식을 사용했습니다.

 

 

전체 코드는 아래와 같습니다.

 

전체 코드

import sys
from collections import deque

N = int(sys.stdin.readline().strip())

mat = [ [-1] * (N+2) if i == 0 or i == N+1 else [-1]+[0]*N+[-1] for i in range(N+2) ]

K = int(sys.stdin.readline().strip())

for _ in range(K):
    r, c = map(int, sys.stdin.readline().strip().split())
    mat[r][c] = 1

L = int(sys.stdin.readline().strip())

dInfo = deque([])

cd = 1
rt = 0
rd = L

for i in range(L):
    x, c = sys.stdin.readline().strip().split()

    x = int(x)

    if i == 0:
        rt = x
        rd = c

    else :
        dInfo.append((x, c))    

dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]

direction = { # (L, D)
    0: (3, 1),
    1: (0, 2),
    2: (1, 3),
    3: (2, 0)
}

snakePos = deque([(1, 1)])
mat[1][1] = -1

answer = 0

while True:
    answer += 1
    
    hr, hc = snakePos[-1]

    if mat[hr+dy[cd]][hc+dx[cd]] == -1:
        break
    elif mat[hr+dy[cd]][hc+dx[cd]] == 0:
        tr, tc = snakePos.popleft()
        mat[tr][tc] = 0

    mat[hr+dy[cd]][hc+dx[cd]] = -1
    snakePos.append((hr+dy[cd], hc+dx[cd]))

    if answer == rt:
        idx = 0

        if rd == "D":
            idx = 1

        cd = direction[cd][idx]

        if len(dInfo) > 0:
            rt, rd = dInfo.popleft()

print(answer)