해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 알고리즘 / 2178번 미로 탐색 - BFS

문제 풀이

이 문제는 BFS로 풀 수 있는 문제입니다. 

(1,1)을 BFS의 queue에 넣고, (1,1)의 위,아래,왼쪽,오른쪽을 검색하여 그 좌표의 값이 1인 경우 그 좌표를 queue에 넣습니다. 그 좌표에 대한 값은 (1,1)의 값에 +1한 값을 넣어줍니다. 

이것을 반복하고, 검색 대상의 좌표가 (N,M)이 되면, 검색하는 값의 +1한 값을 반환합니다. 

그 반환되는 값을 출력하면 이 문제가 해결됩니다. 

위의 과정이 동작된다면, 예제 1번은 아래와 같이 배열의 값들이 계산됩니다.

(N,M)의 값은 검색하는 값인 14의 +1한 값이 되어, 15로 반환됩니다.

 예제 4번은 아래와 같이 배열의 값들이 계산됩니다.

전체 코드

import sys

dcol = [0, 0, 1, -1]
drow = [1, -1, 0, 0]

def isRange(row, col):
	if col >= w or col < 0: return False
	if row >= h or row < 0: return False
	return True

def show():
	for i in range(h):
		for j in range(w):
			print(maps[i][j], end=" ")
		print()

def bfs(row, col) :
	queue = [(row, col)]

	while queue:
		srow, scol = queue.pop(0)

		for i in range(4):
			nrow = srow + drow[i]
			ncol = scol + dcol[i]

			if isRange(nrow, ncol) == False:
				continue
			if nrow == 0 and ncol == 0:
					continue
			if maps[nrow][ncol] != 1:
				continue

			#print ("nrow = ", nrow, ", ncol = ", ncol)
			#show()

			if nrow == h-1 and ncol == w-1:
				return maps[srow][scol] + 1

			maps[nrow][ncol] = maps[srow][scol] + 1
			queue.append((nrow, ncol))



#입력
h,w = map(int, sys.stdin.readline().split())
maps = [list(map(int, input())) for _ in range(h)]

#결과 출력
result = bfs(0, 0)
print(result)