[백준3190&파이썬] 스네이크게임은 deque로 구현이 가능하다.

# 문제

백준 3190 뱀 파이썬 풀이

3190번: 뱀

# 코드

import sys
from collections import deque

def print2D(arr) :
  for i in arr :
    print(i)
  print()

LEFT = 'LEFT'
RIGHT = 'RIGHT'
UP = 'UP'
DOWN = 'DOWN'
DIR_DEFAULT = (0,1,RIGHT)

N = int(sys.stdin.readline().strip())
K = int(sys.stdin.readline().strip())  # 사과의 개수
apples = list()

visit = [['.'] * (N) for _ in range(N)]

def changeDir(fr,to) :
  if fr == LEFT :
    if to == 'L' :
      return (1,0,DOWN)
    if to == 'D' :
      return (-1,0,UP)

  if fr == RIGHT :
    if to == 'L' :
      return (-1,0,UP)
    if to == 'D' :
      return (1,0,DOWN)

  if fr == UP :
    if to == 'L' :
      return (0,-1,LEFT)
    if to == 'D' :
      return (0,1,RIGHT)

  if fr == DOWN :
    if to == 'L' :
      return (0,1,RIGHT)
    if to == 'D' :
      return (0,-1,LEFT)

for _ in range(K):
  row, col = map(int, sys.stdin.readline().split())
  visit[row-1][col-1] = "A"

L = int(sys.stdin.readline().strip())  # 뱀의 방향 회전 횟수
moves = list()

for _ in range(L):
  time, turn = sys.stdin.readline().split()
  moves.append((int(time), turn))

# 자신의 몸에 부딪히면 게임 종료
# 벽에 부딪히면 게임 종료

# 생각해야할 것
# 보드를 그려서 구해야할까? 아니면 그냥 로직적으로 처리할 수 있을까
# 몸길이로 자폭하는 경우만 없다면 그냥 짜도 될텐데..



snakes = deque()
snakes.append((0, 0))
visit[0][0] = "#"
move_top = 0
t = 0
while True:
  t += 1
  snake_head = (snakes[0][0],snakes[0][1]) # 스네이크의 헤드에서 진행방향으로 추가해야함

  tail = snakes.pop()  # (row,col)

  next_head = (snake_head[0] + DIR_DEFAULT[0], snake_head[1] + DIR_DEFAULT[1])
  if (0 <= next_head[0] < N and 0 <= next_head[1] < N) and (visit[next_head[0]][next_head[1]] != "#") :  # 범위 안이면서  몸통이 없는 곳이라면
    visit[tail[0]][tail[1]] = '.'  # 꼬리 부분 뜯기
    if visit[next_head[0]][next_head[1]] == "A" : # 사과를 만나면, 꼬리를 추가시킨다.
      snakes.append((tail[0],tail[1]))
      visit[tail[0]][tail[1]] = '#'

    snakes.appendleft(next_head)
    visit[next_head[0]][next_head[1]] = '#'
  else:
    print(t)
    exit()

  # 시간에 따른 방향 전환
  if move_top < len(moves) :
    time,turn = moves[move_top]
    if time == t :
      DIR_DEFAULT = changeDir(DIR_DEFAULT[2],turn)
      move_top+=1

  # if move_top < len(moves) :
  #   print(t, moves[move_top])
  # print2D(visit)

# 풀이

• 간단한 스네이크 게임을 구현하는 문제이다.
• 이전에 스네이크게임 C++로 프로젝트 했었는데, 그때 정말 말도 안되게 비효율적이게 짰다고 이번에 문제풀면서 느꼈다.
• 스네이크를 이동시키는 전략은 꼬리를 뗀다음에 헤드의 진행방향을 보고 헤드위치 + 진행방향으로 이동시키면 된다.
• 그렇게 하기 위해서 snakes라는 deque를 만들었고, 꼬리를 pop, 머리는 popleft와 같은 논리를 사용했다.
• 처음에는 visit배열 안쓰고 풀어보려했는데, 머리가 자기 몸통에 닿는 경우를 잡아 낼 수가 없다.
• 또한 현재 위치에서 L 또는 R의 회전을 할 수 있는데, 여기서 정확한 로직을 찾기 힘들어서 그냥 하드코딩했다. changd_dir로

# 개선

• 스네이크의 회전을 걸정하기 위해서 change_dir와 같이 하드코딩을 하지 않고도 해결할 수 있다.
• 예를들어 상,우,하,좌의 경우 [ (-1,0) , (0,1), (1,0), (0,-1) ]이고 여기서 우회전을 해야한다면 index를 1증가시키면된다. 역으로 좌회전을 해야한다면 index를 -1을 감소시키면 된다. 그러나 배열이 4개이기 때문에 %4 연산을 이용한다면 방향을 쉽게 결정할 수 있다.