[BFS 알고리즘] 미로 탐색

기출: BOJ #2178

 

n, m = map(int,input().split())
visited = [[False for _ in range(m)]for __ in range(n)]
board = list()
dx,dy = [1,-1,0,0],[0,0,1,-1]

for _ in range(n):
    row = list()
    inputStr = input()
    for j in range(m):
        row.append(int(inputStr[j]))
    board.append(row)

queue = [[[0,0],1]]
visited[0][0] = True

while queue:
    cur = queue.pop(0)
    curX, curY = cur[0][0], cur[0][1]
    curVal = cur[1]
    if curX==n-1 and curY==m-1:
        print(curVal)
        break
    for dir in range(4):
        mx = curX + dx[dir]
        my = curY + dy[dir]
        if mx<0 or my<0 or mx>=n or my>=m: continue
        if visited[mx][my]: continue
        if board[mx][my]==0: continue
        visited[mx][my] = True
        queue.append([[mx,my], curVal+1])