[백준] [Python] 2178번 미로 탐색 - BFS

www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

Python

import sys

row, col = map(int, sys.stdin.readline().split())    
board =[ list(map(int, list(sys.stdin.readline().rstrip()))) for _ in range(row) ]

dx = [0,0,1,-1]
dy = [1,-1,0,0]
visit = [[0 for _ in range(col)] for _ in range(row)]
q = []
cnt = 0
for a in range(row):
    for b in range(col):
        if board[a][b] == 1 and visit[a][b] == 0:
            visit[a][b] = 1
            q.append((a,b))
        
            temp_area = 1
            while (len(q) != 0):
                #print(q)
                pos = q.pop(0)
            
                for i in range(4):
                    nx = pos[0] + dx[i]
                    ny = pos[1] + dy[i]
                    if (0<=nx<row and 0<=ny<col):
                        if (visit[nx][ny] == 0 and board[nx][ny] == 1):
                            visit[nx][ny] = visit[pos[0]][pos[1]]+1
                          
                            if nx==row-1 and ny==col-1:
                                cnt = max(cnt,visit[nx][ny])
                            q.append((nx,ny))

print(cnt)