[BFS]미로 탈출

<이것이 취업을 위한 코딩테스트다>를 공부하며 정리한 내용입니다.

문제

❓ 동빈이는 N X M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 동빈이의 위치는 (1,1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

입력 조건

• 첫째 줄에 두 정수 N, M(4≤N,M≤200)이 주어집니다. 다음 N개의 줄에는 각각 M개의 정수(0 혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이 붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.

출력 조건

• 첫째 줄에 최소 이동 칸의 개수를 출력한다.

입력 예시

5 6

101010

111111

000001

111111

111111

출력 예시

10

---

해설

• BFS 사용
• 미리 상하좌우 변위 리스트로 저장 (구현 느낌..)
• 🍀최단 거리 기록을 각 위치에 갱신해나감
• 처음 가보는 곳을 생각

from collections import deque

n,m=map(int,input().split())

miro=[]
for i in range(n):
    miro.append(list(map(int, input())))

wh=[(1,0),(0,1),(0,-1),(-1,0)]
#가장 가까운 곳부터 살펴야하니까 BFS로...해보자고 ....

def bfs(start):
    go=deque([start]) #방문할 곳 큐에 저장. 가장 처음은 시작점

    while go: #큐가 비어있을 때까지 해야할까 아님 위치가 n.m일때로 해야할까.
        x,y=go.popleft()
        
        for i in wh:
            x0=x+i[0]
            y0=y+i[1]
            #만약 범위에서 넘어가면 이 위치는 아웃
            if x0<0 or x0>=n or y0<0 or y0>=m: 
                continue
            #괴물이 있는 곳이라면
            if  miro[x0][y0]==0:
                continue
            
            #괴물이 없는 처음 가보는 곳이라면
            if miro[x0][y0]==1:
                miro[x0][y0]=miro[x][y]+1 #최단 거리 기록하기
                go.append((x0,y0)) #방문할 곳에 추가
                
    return miro[n-1][m-1]
                
    
print(bfs((0,0)))