문제이해
(0,0)에서 출발해서 (N,M)까지 도착하는데 출발점포함 최소칸수 구하기
갈수없으면 -1
bfs
1. N,M이 주어지지 않아서 주어진 maps으로 구하기
N = len(maps)
M = len(maps[0])2. 최소칸수를 visited방문배열에 +1씩 추가해서 구하기
3.못찾으면 -1반환 위치
# bfs로풀기 최소칸수계산
di = [-1,0,1,0]
dj = [0,1,0,-1]
def bfs(x,y,maps,N,M):
queue = [(x,y)]
visited = [[0]*M for _ in range(N)]
visited[x][y] = 1
while queue:
i,j = queue.pop(0)
if (i,j) == (N-1,M-1):
return visited[i][j]
for d in range(4):
ni = i+di[d]
nj = j+dj[d]
if 0<=ni<N and 0<=nj<M and maps[ni][nj] == 1 and visited[ni][nj] == 0:
queue.append((ni,nj))
visited[ni][nj] = visited[i][j] + 1
return -1
def solution(maps):
N = len(maps)
M = len(maps[0])
return bfs(0,0,maps,N,M)
maps = [[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]]
print(solution(maps))
