[백준 2178] 미로탐색(python)

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

python의 입출력에 익숙해 지지가 않는다 .. 

 

 

풀이

BFS 방법으로 풀었다.

큐에서 pop을 한 후, 그 위치로부터 상 하 좌 우의 좌표를 다시 큐에 넣는다.

이때 주어진 미로에서 벗어나지 않는 범위인지를 체크한다. 

 

이때 cost를 함께 큐에다 넣어주는 방법으로 거리를 count 했다.

from collections import deque 

def BFS(board, finish):
    visited = []
    queue = deque()
    queue.append([[0,0] , 1])
    while queue:
        n, cost = queue.popleft()
        #print("n and cost", n , "  ", cost," board " ,board[n[0]][n[1]])
        if board[n[0]][n[1]] == "0":
            visited.append(n)
            continue    
        if n[0] == finish[0] and n[1] == finish[1]:
            return cost
        if n not in visited:
            visited.append(n)
            if n[0] - 1 >= 0 :
                queue.append([[n[0]-1, n[1]], cost+1])
            if n[0] + 1 <= finish[0]:
                queue.append([[n[0]+1, n[1]], cost+1])
            if n[1] - 1 >= 0:
                queue.append([[n[0], n[1]-1], cost+1]) 
            if n[1] + 1 <= finish[1]:
                queue.append([[n[0], n[1]+1], cost+1]) 
      
#입력
N,M = map(int, input().split(" "))

board = []

for _ in range(N):
    board.append(list(input()))


print(BFS(board, [N-1,M-1]))