-
[백준] 2178. 미로탐색 (BFS)코테 준비/DFS, BFS 2023. 1. 12. 04:35
미로탐색 최단거리를 찾을 때는 BFS를 사용해야함
큰 알고리즘 진행 방법을 외우자!
from collections import deque dx=[-1,1,0,0] dy=[0,0,-1,1] def bfs(x,y): #좌표 queue=deque() queue.append((x,y)) #input 좌표 -시작점 while queue: x,y=queue.popleft() for i in range(4): nx=x+dx[i] ny=y+dy[i] #상하좌우 탐색 if nx<0 or ny<0 or nx>=n or ny>=m: #그래프를 벗어나면 continue if graph[nx][ny]==0: #이동할 수 없는 칸이면 continue if graph[nx][ny]==1: #이동할 수 있는 칸이면 graph[nx][ny]=graph[x][y]+1 #한칸 count queue.append((nx,ny)) return graph[n-1][m-1] #그래프 탈출구까지의 최단거리 n,m=map(int,input().split()) graph=[[0]*m for _ in range(n)] visited=[False]*(n+1) for i in range(n): graph[i]=list(map(int,input())) print(bfs(0,0)) #0,0부터 미로 시작
'코테 준비 > DFS, BFS' 카테고리의 다른 글
[백준] 1697. 숨바꼭질 (다시 풀어보기) (0) 2023.02.02 [백준] 7576. 토마토 (DFS) (0) 2023.01.31 [백준] 1012. 유기농 배추 (2178. 미로탐색과 유사) (0) 2023.01.20 [백준] 11724. 연결요소의 개수 (bfs 무방향 그래프) (0) 2023.01.11 [백준] 2606. 바이러스 (DFS) / 파이썬(Python) (0) 2023.01.06