728x90
반응형
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
✏️ 문제
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
✏️ 풀이
미로에서 최단거리를 구하는 문제다. 최단거리를 구하는 탐색문제의 경우 BFS가 적합하다.
from collections import deque
n,m=map(int,input().split())
matrix=[]
for _ in range(n):
matrix.append(list(map(int,input())))
dx=[-1,1,0,0]
dy=[0,0,1,-1]
def bfs(a,b):
queue=deque([[a,b]])
while(queue):
x,y=queue.popleft()
for i in range(4):
xx=x+dx[i]
yy=y+dy[i]
if 0<=xx<n and 0<=yy<m and matrix[xx][yy]==1:
queue.append([xx,yy])
matrix[xx][yy]=matrix[x][y]+1
bfs(0,0)
print(matrix[n-1][m-1])
728x90
반응형
'프로그래밍 > 백준' 카테고리의 다른 글
백준 11724: 연결요소의 개수 해설- python (0) | 2022.02.11 |
---|---|
백준 2606: 바이러스 해설- python (0) | 2022.02.10 |
백준 10866: 덱 해설- python (0) | 2022.02.06 |
백준 1260: DFS와 BFS 해설 (파이썬, node.js) (0) | 2022.02.06 |
백준 11286: 절댓값 힙 해설- python (0) | 2022.02.06 |