# bfs 소스코드 구현
def bfs(x,y):
# 큐 구현을 위해 deque 라이브러리 사용
queue = deque()
queue.append((x,y))
# 큐가 빌 때까지 반복
while queue:
x,y = queue.popleft()
# 현재 위치에서 4가지 방향으로 위치 확인
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
# 벽인 경우 무시
if graph[nx][ny] == 0:
continue
# 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny))
# 가장 오른쪽 아래까지의 최단 거리 반환
return graph[n-1][m-1]
from collections import deque
n,m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
dx = [-1,1,0,0]
dy = [0,0,-1,1]
print(bfs(0,0))
[Python] 정렬 알고리즘(2)-선택정렬 (0) | 2022.06.19 |
---|---|
[Python] 정렬 알고리즘(1) (0) | 2022.06.19 |
[Python] 그래프 탐색 알고리즘: 음료수 얼려 먹기 (0) | 2022.06.13 |
[Python] 그래프 탐색 알고리즘: BFS (breadth-First Search) (0) | 2022.06.12 |
[Python] 그래프 탐색 알고리즘: DFS (Depth-First Search) (0) | 2022.06.12 |
댓글 영역