[이것이코딩테스트다 Python] 미로 탈출

page 152 미로 탈출

BFS 문제 

 

리스트를 입력받아 0인 괴물을 피해 n,m 좌표로 이동하는데 최소비용을 출력하기

길찾기문제는 BFS로 푸는것이 효율적이기에 BFS풀게되었고 

1일때 지나갈수있는벽 0일때 못지나가는 괴물

이 두가지 조건을 조건문으로 잘 걸러내면 쉽게 풀 수 있는 문제 였습니다.

 

from collections import deque

n,m = map(int, input().split())
maze = []

for _ in range(n):
    maze.append(list(map(int,input())))
    
dx = [0,0,1,-1]
dy = [1,-1,0,0]

def bfs(x,y):
    q = deque()
    q.append((x,y))
    
    while q:
        a,b = q.popleft()
        
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            
            if nx <= -1 or nx >= n or ny <= -1 or ny>=m:
                continue
            
            if maze[nx][ny] == 0:
                continue
            
            if maze[nx][ny] == 1:
                maze[nx][ny] = maze[a][b] +1
                q.append((nx,ny))
    
    return maze[n-1][m-1]
                                           
print(bfs(0,0))