백준 2665 : 미로 만들기 with 파이썬

https://www.acmicpc.net/problem/2665

2665번: 미로만들기

 

1. 검은방을 흰방으로 바꾸는 "최소" 횟수를 구해야 하기 때문에 우선순위큐를 사용

import sys, heapq

input=sys.stdin.readline
n=int(input())
map=[list(map(int, input().strip())) for _ in range(n)]
v=[[False]*n for _ in range(n)]

dy=[0,1,0,-1]
dx=[1,0,-1,0]
def bfs(y,x):
	q=[]
	heapq.heappush(q, (0, y, x))
	while q:
		cnt, qy, qx = heapq.heappop(q)   # heap을 통해 최소 cnt를 꺼내옴
        
		if qy == n-1 and qx == n-1 :
			return cnt
            
		for i in range(4) :   # 최소 cnt를 기준으로 4방향 이동
			ny = qy+dy[i]
			nx = qx+dx[i]

			if 0 <= ny < n and 0 <= nx < n and v[ny][nx]==False:
				v[ny][nx]=True
				if map[ny][nx]==0:   # 검은방일 경우에는 흰방으로 변경
					heapq.heappush(q, (cnt+1, ny, nx))
				
				else : heapq.heappush(q, (cnt, ny, nx))
					
				
		
print(bfs(0,0))