해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 알고리즘 / 1261번 알고스팟 - BFS

www.acmicpc.net/problem/1261

문제 풀이

1261번 알고스팟 문제는 BFS로 풀수 있는 문제입니다. 

deque를 사용하여 queue에 (map의 y좌표, map의 x좌표, 벽을 뚫고간 개수) 세트로 하여 넣습니다. 

(0,0)부터 넣기 시작하고, 4방향을 검사하여 탐색을 합니다.

벽이 없는 좌표에 가중치를 주어 먼저 들어가도록 appendleft() 함수를 사용하면, 4방향 중 벽이 없는 곳부터 계속 탐색해 나가게 됩니다. 벽이 있는 좌표는 append() 함수를 사용하도록 합니다. 

목적지에 도달할 때마다 값을 비교하여 최소 값을 저장하도록 합니다. 

모든 BFS 탐색이 끝난 뒤에는 저장된 최소 값을 반환하여 출력하도록 합니다. 

전체 코드

import sys
from collections import deque
from queue import PriorityQueue

#위, 아래,오른쪽, 왼쪽
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 bfs() :
	#(h, w, defence)
	queue = deque()
	queue.append((0, 0, 0))

	#(h,w)
	visit[0][0] = True
	result_m = 999999999

	while queue:
		sh,sw,sdefence = queue.popleft();

		#queue에서 꺼낸 좌표가 h-1,w-1일 경우 
		if sh == h - 1 and sw == w - 1:
			result_m = min(result_m, sdefence)

		for i in range(4):
			nh = sh + drow[i]
			nw = sw + dcol[i]
			ndefence = sdefence

			if isRange(nh, nw) == False :
				continue

			# 벽이 없는 경우
			if maps[nh][nw] == '0' and visit[nh][nw]== False:
				visit[nh][nw] = True
				queue.appendleft((nh, nw, ndefence))

			# 벽이 있는 경우
			elif maps[nh][nw] == '1' and visit[nh][nw]== False:
					visit[nh][nw] = True
					queue.append((nh, nw, ndefence+1))
	return result_m

#입력
w, h = map(int, sys.stdin.readline().split())
maps = [sys.stdin.readline().rstrip() for _ in range(h)]
visit = [[False]*w for _ in range(h)]

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