[백준 3190 : PYTHON] 뱀

문제 풀기 : 3190번

3190번: 뱀

문제

NxN 정사각 보드위에서 진행한다.

몇몇 칸에는 사과가 놓여져 있다.

보드의 상하좌우 끝에 벽이 있다.

뱀은 맨위 맨좌측에 위치한다. 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

 

문제풀이

1. 뱀의 위치를 큐에 넣어서 보관한다. 뱀이 이동할 때 머리와 꼬리의 변화만 있기 때문이다. 배열말고 큐를 사용하는 이유는 삽입, 삭제 시 logN만큼의 시간이 걸리기 때문에 효율성이 좋다.

2. 뱀이 움직이는 방향 인덱스 변수(idx)를 만들어서 인덱스번호에 맞춰 move배열에 배치시킨다.

제 경우엔 왼쪽으로 90도 돌렸을 때의 방향들 순으로 배치했다. (오른쪽 → 위 → 왼쪽 → 아래)

오른쪽 90도의 경우에는 인덱스 반대방향이다.

3. X(초), C(방향)는 각각 따로 배열에 저장한다. while 문으로 1초씩 움직이면서 X에 방향 바꿀 시간이 되면 방향의 타입(L 또는 D)에 따라 뱀의 방향(idx)을 바꿔준다.

방향 바꿀 시간이 아니라면, 뱀의 다음 방향(nx, ny)이

• 벽이나 자기 자신이라면 while문을 빠져 나가고
• 사과라면 현재 사과 위치를 snake 큐 맨앞에 넣어 뱀의 몸 길이를 늘린다. 사과를 먹었으므로 사과 위치(7)를 뱀이 지나다닐 수 있는 위치(0)으로 바꿔준다.
• 사과가 아니면 다음 위치를 뱀의 머리(큐 맨앞)에 위치시키고 꼬리 위치(큐 맨끝)를 없앤다.

4. 카운트는 뱀이 시작할 때 시작 위치에 위치하는 시간까지 포함해야 하므로 +1을 해준다.

 

전체코드

import sys
input = sys.stdin.readline
from collections import deque

# 뱀의 현재위치
snake = deque()
snake.appendleft([0,0])

# 왼쪽 90도 기준 (오, 위, 왼, 아)
move = [[0, 1], [-1, 0], [0, -1], [1, 0]]

# 뱀의 현재 방향
idx = 0

# INPUT
N = int(input())
board = [[0] * N for _ in range(N)]

K = int(input())
for _ in range(K):
    x, y = map(int, input().split())
    # 사과 위치 표시
    board[x-1][y-1] = 7

# 게임 시간
sec = 0

L = int(input())
X = []
C = []
for i in range(L):
    t1, t2 = input().split()
    X.append(int(t1))
    C.append(t2)

while True:
    # 방향 바꾸는 시간이 되었을 때
    if sec in X:
        # 방향바꾸기
        d = C[X.index(sec)]    
        
        # 왼쪽 90도
        if d == 'L':
            idx = (idx + 1) % 4
        # 오른쪽 90도
        else:
            if (idx - 1) == -1:
                idx = 3
            else:
                idx = (idx - 1) % 4

    nx = snake[0][0] + move[idx][0]
    ny = snake[0][1] + move[idx][1]

    # 벽에 부딪히거나 자기 자신을 만났을 때
    if nx < 0 or ny < 0 or nx > N-1 or ny > N-1 or ([nx, ny] in snake) :
        break
    # 사과일 때
    if board[nx][ny] == 7:
        snake.appendleft([nx, ny])
        board[nx][ny] = 0
    # 사과 아닐 때
    else:
        # 머리 위치 변경, 꼬리 줄이기
        snake.appendleft([nx, ny])
        snake.pop()

    sec += 1
        
# 뱀이 처음 시작자리에 놓이는 시간 포함  
print(sec + 1)