BFS 기본예제임
이전에 올렸던 BFS 알고리즘 포스팅 내용을 참고하면 좋을 것 같다.
BFS는 경로탐색시 가장 적은 개수의 간선을 가지는 방향을 우선적으로 탐색하게 된다. 미로탐색 문제의 경우 인접한 노드간의 거리가 일정하기 때문에 간선이 최소로 목적지에 도착하는 경로가 최단경로가 된다.
#BFS
from collections import deque
N,M=map(int,input().split())
miro=[]
miro=[list(map(int,input())) for _ in range(N)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
def bfs(x,y):
queue=deque([[x,y]])
# queue.append([x,y])
while queue:
x,y=queue.popleft()
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if not (nx<0 or ny<0 or nx>N-1 or ny>M-1 or miro[x][y]==0):
if miro[nx][ny]==1:
miro[nx][ny]=miro[x][y]+1
queue.append((nx,ny))
return miro[N-1][M-1]
print(bfs(0,0))https://www.acmicpc.net/problem/2178
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
#관련 포스팅
https://campkim.tistory.com/12
DFS / BFS 알고리즘과 예제풀이 ( 백준 바이러스, BFS 와 BFS 파이썬 )
대표적인 그래프탐색 알고리즘 DFS, BFS 핵심 요약 및 백준 기본문제풀이. *하기 글에서 노드(node), 정점(vertex)를 혼용해서 사용하는데 동일한 것을 의미함 BFS (Breadth First Search, 너비 우선 탐색) Intro
campkim.tistory.com
'자료구조 알고리즘 > 알고리즘' 카테고리의 다른 글
| 백준 3055 탈출 파이썬 BFS 풀이 (0) | 2021.08.25 |
|---|---|
| 백준 동전 2294 BFS 파이썬 문제풀이 (0) | 2021.08.25 |
| [파이썬] 백준 11725 트리의 부모찾기 ( BFS, DFS 3가지 풀이 비교) (0) | 2021.08.25 |
| DFS / BFS 알고리즘과 예제풀이 ( 백준 바이러스, BFS 와 BFS 파이썬 ) (0) | 2021.08.25 |
| 그래프 기본 개념 정리 (0) | 2021.08.25 |