[백준] 3190 파이썬(python) : 뱀 - (★)

3190번: 뱀

 

 

시뮬레이션 문제는 어렵다. 조건들을 구현하는것이 상당히 까다롭다.

 

import sys
from collections import deque
n = int(sys.stdin.readline())
k = int(sys.stdin.readline())

graph = [ [0]*(n) for _ in range(n) ]
dx = [ 0, 1, 0, -1 ] #1
dy = [ 1, 0, -1, 0 ]

for _ in range(k):
    a, b = map(int, sys.stdin.readline().split())
    graph[a-1][b-1] = 2 #2

l = int(sys.stdin.readline())
step = {}
q = deque()
q.append((0, 0)) #3

for _ in range(l):
    x, c = sys.stdin.readline().rstrip().split()
    step[int(x)] = c #4

x, y = 0, 0
graph[x][y] = 1 #5
cnt = 0 #6
direction = 0 #7

def turn(alpha):
    global direction
    if alpha == 'L': #8
        direction = (direction - 1) % 4
    else:
        direction = (direction + 1) % 4

while True:
    cnt += 1 #9
    x += dx[direction] #10
    y += dy[direction]
    if x < 0 or x >= n or y < 0 or y >= n: #11
        break
    if graph[x][y] == 2: #12
        graph[x][y] = 1
        q.append((x, y))
        if cnt in step: #13
            turn(step[cnt])
            
    elif graph[x][y] == 0:
        graph[x][y] = 1
        q.append((x, y))
        tx, ty = q.popleft() #14
        graph[tx][ty] = 0
        if cnt in step:
            turn(step[cnt])
    else:
        break
print(cnt)

 

#1 : 방향벡터의 순서를 신경써야한다. 뱀의 머리는 맨 처름 오른쪽을 향하고 있다고 했으므로 첫번째는 (0, 1)을 넣어서 동쪽을 향하게 하고 'L'과 'D'가 나올때마다 반시계방향으로 90도 시계방향으로 90도 머리의 방향을 회전하므로 동쪽 다음은 90도 시계방향회전인 남쪽(1, 0)이 나오고 그 다음은 남쪽에서 90도 회전한 서쪽이 나오고 마지막은 북쪽이 나온다.

동쪽에서 -90도를 회전해도 마지막 리스트로 움직이는데 북쪽이어야 한다.

#2 : 사과가 있는 위치를 입력받아서 그래프안에 2로 저장

#3 : q는 뱀이 이동하는 구간을 의미하고 시작위치를 삽입

#4 : 입력받은 숫자로 해시에 방향 입력

#5 : 시작위치 방문처리

#6 : 시간을 세어줄 변수 생성

#7 : 방향벡터변수 생성, 처음은 동쪽이 시작이니까 0으로 초기화

#8 : 해시를 이용해 특정시간이 되었을때 'L'인지 'D'인지를 확인

#9 : 해시 value가 'L'이라면 direction에 -1을 하고 %4, 'D'라면 +1을 하고 %4

(-1 % 4 = 3이 된다, 파이썬 기준)

#10 : 시간 추가

#11 : 방향만큼 한칸이동

#12 : 범위를 벗어나면 break

#13 : 새롭게 이동한 칸이 사과가 있는 장소라면, 위치를 뱀이 있는곳으로 갱신, 위치 q에 삽입

#14 : 만일 특정 시간이 해시안에 있다면, 해시 value에 해당하는 회전

#15 : 새롭게 이동한 칸이 사과가 없는 장소라면, 이동 후 꼬리를 지워주어야함. 가장 처음에 q에 넣었던 뱀의 이동위치를 꺼내서 0으로 갱신

 

큐 문제인데 popleft를 사용하기 위해 deque을 사용하고 방향벡터도 사용했는데 변형된 bfs문제 같았다.

시뮬레이션 문제는 많은 유형의 문제를 풀고 복습이 필요할것 같다.