백준2178번 미로탐색(BFS)
문제 : https://www.acmicpc.net/problem/2178
최단거리이기 때문에 BFS를 사용한다.
다시정리:
DFS 스택사용, 이동과정을 할때 주로계산
BFS 큐 사용 , 최단거리 계산할때 주로계산
미로같은 탐색을 할때에는 상하좌우에 대한 좌표를 설정해야한다.
(이런 패턴을 외워둬야할듯..)
상하좌우
dx = [-1,1,0,0]
dy = [0,0,-1,1]
입력받는값
N,M = map(int,input().split())
for i in range(N):
graph.append(list(map(int,input().strip())))
-> MAP = [[int(i) for i in list(input())] for _ in range(N)] 가능하다함.
만약 strip이 아닌 split()로 하면 아래와 같은 값이나옴
[[101111], [101010], [101011], [111011]]
strip경우
[[1, 0, 1, 1, 1, 1], [1, 0, 1, 0, 1, 0], [1, 0, 1, 0, 1, 1], [1, 1, 1, 0, 1, 1]]
from collections import deque
def bfs(x,y):
queue = deque()
queue.append((x,y))
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
if graph[nx][ny] == 0:
continue
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y]+1
queue.append((nx,ny))
return graph[-1][-1]
#graph[N-1][M-1]
N,M = map(int,input().split())
graph = []
for i in range(N):
graph.append(list(map(int,input().strip())))
dx = [-1,1,0,0]
dy = [0,0,-1,1]
print(bfs(0,0))
Author And Source
이 문제에 관하여(백준2178번 미로탐색(BFS)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kujin2/백준2178번-미로탐색BFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)