백준 파이썬 2178 미로 탐색

백준 링크:https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

BFS로 풀이하였다. 보통 최단거리를 계산하는 문제는 BFS로 해야 쾌적하다고 들었다.

 

BFS로 자리를 찾아가며

 

첫 자리가 S[0][0]이 1이라면 다음 자리는 2이므로 S[1][0]은 S[0][0] + 1 로 계산하였다.

복사한 예제의 수열 s를 출력해보면

순서따라 숫자가 잘 출력된것을 볼 수 있다.

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

s=[list(input()) for i in range(n)]

nx=[-1,1,0,0]
ny=[0,0,-1,1]

visited=[[0,0]]
s[0][0] = 1


while visited:
    a,b=visited[0][0],visited[0][1]

    del visited[0]

    for i in range(4):
        xx=a+nx[i]
        yy=b+ny[i]
        if n > xx >= 0 and m > yy >= 0:
            if s[xx][yy] == '1':
                visited.append([xx,yy])
                s[xx][yy] = s[a][b] + 1
print(s[n-1][m-1])