[ baekjoon ] 3190. 蛇.

3190.蛇

質問する

「Dummy」というドスゲームがありました.このゲームには蛇が這い出していて、りんごを食べると蛇の長さが増えます.ヘビが這い回って、壁や自分の体にぶつかって、ゲームは終わりました.
ゲームはNxN正方形の碁盤で行われ、一部の格にはりんごが置かれている.板の上下左右端に壁があります.ゲーム開始時、ヘビは一番上の一番左側にあり、ヘビの長さは1です.蛇は最初は右です.
ヘビは毎秒移動し、次のルールに従います.
まず、蛇は体の長さを伸ばして、頭を次の節に位置させます.
移動する格子の中にりんごが入っていれば、格子の中のりんごはなくなり、しっぽが動かなくなります.
動く格子にリンゴがなければ、体長を縮めて尻尾のある格子を出す.つまり、身長は変わらない.
リンゴの位置と蛇の移動経路を与えると,このゲームは数秒で終了する.

入力

最初の行は、プレートのサイズNを与える.(2≦N≦100)次の行はリンゴの個数Kを与える.(0 ≤ K ≤ 100)
次のK行はリンゴの位置を示し,1番目の整数は行を表し,2番目の整数は列の位置を表す.りんごの位置が違います.一番上の左側(1行1列)にはりんごがありません.
次の行は蛇の方向転換回数Lを与える.(1 ≤ L ≤ 100)
以下のL行は蛇の方向変換情報を提供し,整数Xと文字Cからなる.ゲーム開始時間からX秒終了後に左(Cは「L」)または右(Cは「D」)に90度回転します.Xは10000以下の正の整数であり、方向変換情報はXが増加する順に与えられる.

しゅつりょく

1行目の出力ゲームは数秒で終了します.

## 3190. 뱀
from collections import deque
import sys

input = sys.stdin.readline

n = int(input()) # 보드의 크기
board = [[0 for col in range(n)] for row in range(n)]

k = int(input())

apples = []
for _ in range(k): # 사과 위치 입력 받기
  r, c = map(int, input().split()) 
  board[r - 1][c - 1] = 1

l = int(input()) # 뱀 방향 변환 횟수
directions = dict()

for _ in range(l): # 방향 변환 정보 입력 받기
  x, c = input().split()
  directions[int(x)] = c

# 0 : 사과 존재 X
# 1 : 사과 존재 O
# 2 : 뱀 존재 

dc = [1, 0, -1, 0] 
dr = [0, 1, 0, -1]  # 우 하 좌 상

idx = 0 # 방향 변수(+1 : 오른쪽, -1 : 왼쪽)
r = c = 0

second = 0

q = deque([(0, 0)]) # 뱀이 지나간 곳 저장하자 # tail 계속 바뀜
def check_range(length, r, c):
  if r < 0 or c < 0 or r >= length or c >= length:
    return False
  else: return True

while True:
  # 1초뒤 이동할 좌표가 부딪히거나 자기 몸에 부딪혔을 때 
  tmp_r = r + dr[idx]
  tmp_c = c + dc[idx]
  if not check_range(n, tmp_r, tmp_c) or board[tmp_r][tmp_c] == 2:
    print(second + 1)
    break
  else:
    second += 1
    r, c = tmp_r, tmp_c
    q.append((r, c))
    if  board[r][c] == 1: # 사과가 있는 경우
      pass

    else: 
      tail = q.popleft() # 꼬리 이동
      board[tail[0]][tail[1]] = 0
    
    board[r][c] = 2

    # 방향 전환 체크
    if second in directions.keys():
      if directions[second] == 'L':
        idx = (idx - 1) % 4
      else:
        idx = (idx + 1) % 4

コードを書くとき、
3番目のルールの尻尾にスペースを空ける条件があるからです.
行列に入ることを宣言し、蛇のいる格子を増やした.
だからリンゴがなければ、popleftを通じてtailの位置を次の位置に移動します.
そして移動可能な位置であれば、その位置はappendです.
ちょっと考えて、コードを書いておけば、解けそう!