https://programmers.co.kr/learn/courses/30/lessons/1844
알고리즘 분류
- BFS
문제풀이
백준에서 많이 연습했던 전형적인 BFS문제였다.
[[1, 0, 1, 1, 1], [2, 0, 1, 0, 1], [1, 0, 1, 1, 1], [1, 1, 1, 0, 1], [0, 0, 0, 0, 1]]
[[1, 0, 1, 1, 1], [2, 0, 1, 0, 1], [3, 0, 1, 1, 1], [1, 1, 1, 0, 1], [0, 0, 0, 0, 1]]
[[3, 0, 1, 1, 1], [2, 0, 1, 0, 1], [3, 0, 1, 1, 1], [1, 1, 1, 0, 1], [0, 0, 0, 0, 1]]
[[3, 0, 1, 1, 1], [2, 0, 1, 0, 1], [3, 0, 1, 1, 1], [4, 1, 1, 0, 1], [0, 0, 0, 0, 1]]
[[3, 0, 1, 1, 1], [2, 0, 1, 0, 1], [3, 0, 1, 1, 1], [4, 5, 1, 0, 1], [0, 0, 0, 0, 1]]
[[3, 0, 1, 1, 1], [2, 0, 1, 0, 1], [3, 0, 1, 1, 1], [4, 5, 6, 0, 1], [0, 0, 0, 0, 1]]
[[3, 0, 1, 1, 1], [2, 0, 1, 0, 1], [3, 0, 7, 1, 1], [4, 5, 6, 0, 1], [0, 0, 0, 0, 1]]
[[3, 0, 1, 1, 1], [2, 0, 8, 0, 1], [3, 0, 7, 1, 1], [4, 5, 6, 0, 1], [0, 0, 0, 0, 1]]
[[3, 0, 1, 1, 1], [2, 0, 8, 0, 1], [3, 0, 7, 8, 1], [4, 5, 6, 0, 1], [0, 0, 0, 0, 1]]
[[3, 0, 9, 1, 1], [2, 0, 8, 0, 1], [3, 0, 7, 8, 1], [4, 5, 6, 0, 1], [0, 0, 0, 0, 1]]
[[3, 0, 9, 1, 1], [2, 0, 8, 0, 1], [3, 0, 7, 8, 9], [4, 5, 6, 0, 1], [0, 0, 0, 0, 1]]
[[3, 0, 9, 10, 1], [2, 0, 8, 0, 1], [3, 0, 7, 8, 9], [4, 5, 6, 0, 1], [0, 0, 0, 0, 1]]
[[3, 0, 9, 10, 1], [2, 0, 8, 0, 1], [3, 0, 7, 8, 9], [4, 5, 6, 0, 10], [0, 0, 0, 0, 1]]
[[3, 0, 9, 10, 1], [2, 0, 8, 0, 10], [3, 0, 7, 8, 9], [4, 5, 6, 0, 10], [0, 0, 0, 0, 1]]
[[3, 0, 9, 10, 11], [2, 0, 8, 0, 10], [3, 0, 7, 8, 9], [4, 5, 6, 0, 10], [0, 0, 0, 0, 1]]
[[3, 0, 9, 10, 11], [2, 0, 8, 0, 10], [3, 0, 7, 8, 9], [4, 5, 6, 0, 10], [0, 0, 0, 0, 11]]
다음과 같은 방식으로 BFS로 퍼져나가면서 1일 경우 이전 값+1을 해간다.
그 이후 n,m에 해당하는 값을 구해주면 정답이다.
소스코드
from collections import deque
def solution(maps):
dx=[1,-1,0,0]
dy=[0,0,1,-1]
n,m=len(maps),len(maps[0])
queue=deque()
queue.append((0,0))
while queue:
x,y=queue.popleft()
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if nx<0 or nx>=n or ny<0 or ny>=m:
continue
elif maps[nx][ny]==1:
maps[nx][ny]=maps[x][y]+1
queue.append((nx,ny))
#print(maps)
if maps[n-1][m-1]==1:
return -1
return maps[n-1][m-1]