해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 알고리즘 / 2206번 벽 부수고 이동하기 - BFS

www.acmicpc.net/problem/2206

문제 풀이 

2206번 벽 부수고 이동하기 문제는 BFS로 풀 수 있는 문제입니다. 

Queue에 (h, w, defence, cnt)를 넣고, bfs를 돌립니다. 

그리고 visit[h][w][defence]를 만들어, 방문했는지를 기록합니다. defence는 벽을 한번 통과 했는지, 통과하지 않았는지에 대한 정보입니다 .

Queue에 있는 정보를 꺼내었을 때, 위,아래,왼쪽,오른쪽을 검색하면서, 벽이 없다면 방문했는지를 검사하고 그 좌표를 Queue에 넣어줍니다. 벽이 있다면, 현재 벽을 한번 뚫었는지 검사하여, 한번도 뚫지 않았다면, 방문했는지 검사하고 그 좌표를 Queue에 넣어줍니다. Queue에 넣어줄 때에는 cnt를 +1해줍니다. 

Queue에 있는 정보를 꺼내었을 때, 입력한 N, M 값이면 cnt를 반환하여 출력합니다. 

Queue가 비어있는데, cnt를 반환하지 못하였다면 -1를 출력해줍니다. 

전체 코드

import sys
from collections import deque

#위, 아래,오른쪽, 왼쪽 
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, count)
	queue = deque()
	queue.append((0, 0, 1, 1))

	#(h,w,defence)
	visit[0][0][1] = True

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

		#queue에서 꺼낸 좌표가 h-1,w-1일 경우 결과값 반환
		if sh == h - 1 and sw == w - 1:
			return scnt

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

			if isRange(nh, nw) == False :
				continue
			
			# 벽이 없는 경우 
			if maps[nh][nw] == '0' and visit[nh][nw][ndefence] == False:
				visit[nh][nw][ndefence] = True
				queue.append((nh, nw, ndefence, ncnt))
				
			# 벽이 있는 경우
			elif maps[nh][nw] == '1' and visit[nh][nw][ndefence] == False:
				if ndefence == 1: #벽을 한번 뚫었는지 검사
					ndefence = 0
					visit[nh][nw][ndefence] = True
					queue.append((nh, nw, ndefence, ncnt))
	return -1

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

result = 0
result = bfs()
print(result)