[Python] BOJ 3190 - 뱀(zmija)

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

3190번: 뱀

요즘 구현, 시뮬레이션 문제들을 미는 중인데 삼성기출을 풀다 백준문제를 푸니 확실히 쉽게(?) 느껴진다.

시뮬레이션 문제는 말 그대로 주어진 조건을 따라 시뮬레이션을 돌리면 된다.

골드 이상부터는 엄청난 집중력과 끈기, 인내가 필요하다.. (빡구현, 하드코딩)

 

1. 사과위치를 입력받고 정사각보드m에 사과위치를 -1로 표시해준다.

 

2. 방향변환정보를 turn이라는 dictionary에 저장한다. 예제 1같은 경우는 turn = {3: 'D', 15: 'L', 17: 'D'}와 같이 저장된다.

 

3. 이제 규칙에 따라 시뮬레이션을 돌린다. 처음에 방향이 오른쪽을 향하므로 dir = 0으로 설정한다.

   오른쪽일 때 dir이 0 이므로 dx와 dy배열을 설정할때 dx[0], dy[0]이 오른쪽으로 진행되도록

   미리 설정해놓는 것이 keypoint!

   처음에 몸길이가 1이고 0,0에 있으므로 body라는 deque에 (0,0)을 넣는다.

 

4. 시간을 1증가시킨다. headx, heady에는 body의 첫번째 인덱스의 첫번째 값, body의 첫번째 인덱스의

   두번째 값을 넣고 tailx, taily에는 body의 마지막 인덱스의 첫번째 값, body의 마지막 인덱스의

   두번째 값을 넣어준다.

   (body라는 덱은 실제 뱀의 몸처럼 맨 앞좌표가 머리좌표이고 맨 마지막 좌표가 꼬리좌표이다.)

 

5. '먼저 머리를 다음칸에 위치시킨다' 라고 했으므로 headx와 heady를 다음칸으로 이동시킨다.

    headx나 heady가 좌표를 벗어나거나 (headx, heady)가 body라는 덱에 이미 존재한다면(머리가 몸에 닿는

    경우) time을 출력하고 빠져나온다.

 

6. 5번에서 break에 안 걸리면 내려와서 다음 규칙을 따른다.

   이동한 칸에 사과가 있으면, 사과를 없애고 body의 맨 앞에 headx, heady를 append해준다

   -> 원래의 머리좌표가 한칸 뒤로가고 새로운 머리좌표가 body의 첫번째로 오게된다.

 

7. 이동한 칸에 사과가 없다면, 꼬리좌표를 없애야하므로 body.pop()을 하고 새로운 머리좌표를 appendleft해준다.

 

8. 이동을 마친 뒤 만약 현재 time에서 방향 전환을 해야 한다면(time in turn), if문을 사용해 현재 방향에 따라

    알맞게 다음 방향으로 dir를 바꿔준다.

 

from collections import deque
import sys
input = sys.stdin.readline
turn = {}
dx, dy = [0,0,-1,1], [1,-1,0,0]
N = int(input())
m = [[0] * N for _ in range(N)]
for _ in range(int(input())):
	r, c = map(int,input().split())
	m[r-1][c-1] = -1
for _ in range(int(input())):
	x, c = input().split()
	turn[int(x)] = c
dir, time = 0, 0
body = deque([(0,0)])
while True:
	time += 1
	headx, heady = body[0][0], body[0][1]
	tailx, taily = body[-1][0], body[-1][1]
	headx, heady = headx + dx[dir], heady + dy[dir]
	if headx < 0 or headx >= N or heady < 0 or heady >= N or (headx, heady) in body:
		print(time)
		break
	if m[headx][heady] == -1:
		m[headx][heady] = 0
		body.appendleft((headx, heady))
	else:
		body.pop()
		body.appendleft((headx, heady))
	if time in turn:
		if dir == 0:
			dir = 3 if turn[time] == 'D' else 2
		elif dir == 1:
			dir = 2 if turn[time] == 'D' else 3
		elif dir == 2:
			dir = 0 if turn[time] == 'D' else 1
		elif dir == 3:
			dir = 1 if turn[time] == 'D' else 0

(solved.ac 티어: 골드 5)

 

# 똑같은 골드 5문제들인데, 확실히 삼성기출문제들은 훨씬 어렵다.. (난이도 수정 시급..)