maps | answer |
---|---|
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] | 11 |
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] | -1 |
0과 1로만 나뉘어 1인 곳은 모두 갈 수 있는데 (0,0) 부터 (n,m)까지 지나가야 하는 칸의 개수의 최솟값 구하기
=> BFS
from collections import deque
def bfs(maps, visited, n, m):
visited[0][0] = 1
q = deque()
q.append((0, 0))
dx = [-1,1,0,0]
dy = [0,0,-1,1]
while q:
x, y = q.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0<=nx<n and 0<=ny<m:
if maps[nx][ny] == 1 and visited[nx][ny] == -1:
visited[nx][ny] = visited[x][y] + 1
q.append((nx, ny))
return visited[-1][-1]
def solution(maps):
n = len(maps)
m = len(maps[0])
visited = [[-1]*m for _ in range(n)]
return bfs(maps, visited, n, m)