[백준] 3190 뱀 python 풀이

문제

• 난이도: 골드4
• 알고리즘 분류: 구현, 자료구조, 시뮬레이션, 덱, 큐
• 요약: 뱀이 기어다니다가 벽 또는 자기자신의 몸과 부딪혔을 때까지의 시간 구하기

풀이

board 정의하기

• 빈 칸: 0 (정의 시 0으로 초기화)
• 뱀: 1
• 사과: 2

뱀의 위치를 queue에 저장하기

queue에 뱀이 차지하고 있는 위치를 [row, col] 형태로 저장

• 이동한 칸에 사과가 있을 경우
  몸 길이 늘리기: board 상태 업데이트 & queue에 위치 추가

• 이동한 칸에 사과가 없을 경우
  몸 길이 늘리기 (+1)
  꼬리가 위치한 칸 비우기: popleft 연산을 통해 가장 먼저 queue에 추가된 요소를 꺼내오는 작업을 수행 (-1)
  따라서 몸 길이 변화 x

코드

from collections import deque
import sys

input = sys.stdin.readline

n = int(input())
board = [[0] * n for _ in range(n)]

k = int(input()) # 사과의 개수
for _ in range(k):
	r, c = map(int, input().split())
	board[r-1][c-1] = 2

l = int(input()) # 방향 변환 횟수
change = dict()
for _ in range(l):
	time, dir = input().split()
	change[int(time)] = dir

#     동  남  서  북
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def turn(alpha):
	global dir

	if alpha == 'L':
		# 왼쪽으로 90도 회전
		dir = (dir - 1) % 4
	elif alpha == 'D':
		# 오른쪽으로 90도 회전
		dir = (dir + 1) % 4

board[0][0] = 1 # 시작 위치
y, x = 0, 0 # 시작 행, 열 초기화
dir = 0 # 오른쪽 방향부터 시작
time = 0 # 진행 시간

snake = deque() # 뱀의 위치
snake.append([0, 0])

while True:
	time += 1

	x += dx[dir]
	y += dy[dir]

	if not(0 <= y < n and 0 <= x < n):
		break

	if board[y][x] == 1: # 자기자신의 몸과 부딪혔을 때
		break

	elif board[y][x] == 2:
		# 몸길이 늘리기
		board[y][x] = 1
		snake.append([y, x])
	
	elif board[y][x] == 0:
		# 몸길이 늘리기
		board[y][x] = 1
		snake.append([y, x])
		# 꼬리 비우기
		tail_y, tail_x = snake.popleft()
		board[tail_y][tail_x] = 0
	
	# 방향 전환 정보 확인
	if time in change:
		turn(change[time])

print(time)