(Python) - BOJ(3190번) : 뱀

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

3190번: 뱀

---

• 해설 : 

 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

 

 

 

---

• 풀이 :

BFS로 가로, 세로를 탐색하며 몸 길이를 늘릴 수 있는지(탐색이 가능한지)와 사과가 있는지에 대한 경우를 확인하며 조건에 해당하는 행동을 취한다.

 

 

 

---

• 소스코드 : 

 

from collections import deque
import sys
# 상 하 좌 우
dx = [0,1,0,-1]
dy = [1,0,-1,0]
 
def bfs():
    queue = deque([[0,0]])
    cnt = 0
    curr = 0
    i=0
    maps[0][0] = 2
    tale = deque([[0,0]])
    while queue:
        x,y = queue.popleft()
        if cnt == turn[i][0]:
            if turn[i][1] == "D":
                curr = (curr+1)%4
            else:
                curr = (curr-1)%4
            if i < len(turn)-1:
                i+=1
        ax = x + dx[curr]
        ay = y + dy[curr]
        cnt += 1
        if 0 <= ax < N and 0 <= ay < N:
            if maps[ax][ay] == 2:
                return cnt
            elif maps[ax][ay] == 0:
                a,b = tale.popleft()
                maps[a][b] = 0
                maps[ax][ay] = 2
                queue.append([ax,ay])
            elif maps[ax][ay] == 1:
                maps[ax][ay] = 2
                queue.append([ax,ay])
            tale.append([ax,ay])
        else:
            return cnt
if __name__ == "__main__":
    N = int(sys.stdin.readline())
    K = int(sys.stdin.readline())
    maps = [[0]*N for _ in range(N)]
    for _ in range(K):
        a, b = map(int,sys.stdin.readline().split())
        maps[a-1][b-1] = 1
    L = int(sys.stdin.readline())
    turn = []
    for _ in range(L):
        a, b = sys.stdin.readline().split()
        turn.append([int(a),b])
 
    print(bfs())