미로 탐색 풀이

문제 링크: https://www.acmicpc.net/problem/2178

백준 알고리즘 기초 2/2 600에서 7번째 - 2178번 미로 탐색을 풀어보았다.

 

풀이: https://jokerldg.github.io/algorithm/2021/03/24/maze.html 를 참고해 bfs를 썼다. 

 

C++

 

Python

from collections import deque

def bfs(a,b):
	dx=[-1,1,0,0]
	dy=[0,0,-1,1]
	queue=deque()
	queue.append((a,b))
	while queue:
		a,b=queue.popleft()
		for i in range(4):
			na=a+dx[i]
			nb=b+dy[i]
			if na<0 or na>=n or nb<0 or nb>=m:
				continue
			if graph[na][nb]==0:
				continue
			if graph[na][nb]==1:
				graph[na][nb]=graph[a][b]+1
				queue.append((na,nb))
	return graph[n-1][m-1]

n,m=map(int,input().split())
graph=[]
for i in range(n):
	graph.append(list(map(int,input())))
print(bfs(0,0))

Java