[python] 백준 3190번: 뱀

https://www.acmicpc.net/problem/3190

3190번: 뱀

 

삼성 sw역량테스트 문제

 

테마

구현, 큐

 

설명

 

2차원 배열에서의 큐, 방향 전환, 인덱스 예외처리 등을 고려해서 풀어야 한다.

 

배운 것들

1. 모듈로 연산을 통한 Left,Right move 방향 전환.

2. Queue 를 이용한 꼬리 자르기. deque 의 appendleft 활용한 큐 복구

 

from sys import stdin
from collections import deque

def is_exception(x,y):
    global board,N
    if x > N or y > N or x < 1 or y < 1:
        return True
    if board[x][y] == 1:
        return True
    return False

move = [[0,1],[1,0],[0,-1],[-1,0]]
# 1->4 : right
# 4->1 : left
N = int(input())
K = int(input())
board = [[0]*(N+1) for _ in range(N+1)]
commands = ['']*(10000+1)
for _ in range(K):
    row,col = map(int,stdin.readline().split())
    board[row][col] = 2
L= int(input())
for _ in range(L):
    time,dir = stdin.readline().split()
    commands[int(time)] = dir


direction = 0
#     right
now_x,now_y = 1,1
tails = deque()
tails.append((1,1))
t = 0
while True:
    t += 1
    now_x += move[direction][0]
    now_y += move[direction][1]
    tail = tails.popleft()

    if is_exception(now_x,now_y):
        print(t)
        exit()
    board[tail[0]][tail[1]] = 0
    if board[now_x][now_y] == 0: # non apple
        board[now_x][now_y] = 1
    elif board[now_x][now_y] == 2: # apple
        board[now_x][now_y] = 1
        board[tail[0]][tail[1]] = 1
        tails.appendleft(tail)

    tails.append((now_x,now_y))

    if commands[t] == 'L':
        direction = (direction - 1) % 4
    elif commands[t] == 'D':
        direction = (direction + 1) % 4

 

다음 차례의 x,y 좌표에 대해, 그 위치가 사과가 있나 없나 체크하기 전에 꼬리가 먼저 남아있어야하나, 꼬리가 이동해있어야 하나. 그 순서때문에 많이 헷갈렸다.

 

머리가 이동할 수 있나 없나를 체크할 때는 꼬리의 위치는 움직여지지 않아야 하는게 맞다.