[파이썬] 백준 2665 : 미로만들기 (골드4)

[파이썬] 백준 2665 : 미로만들기 (골드4)

2665번: 미로만들기

---

문제

---

풀이

방향성 생각

• 0이면 부수면서 부순 횟수 카운트, 1이면 그냥 이동
• 힙에다가 부순횟수 저장해서 push, pop

전체코드

import heapq as hq
import sys
input = lambda : sys.stdin.readline().rstrip()

n = int(input())
arr = [list(input()) for _ in range(n)]

dire = [(1,0),(0,1),(-1,0),(0,-1)]
visit = [[50**2]*n for _ in range(n)]
visit[0][0] = 0

heap = [(0,0,0)]
while heap:
    
    c,x,y = hq.heappop(heap)
    
    if (x,y) == (n-1,n-1):
        print(c)
        
    for dx,dy in dire:
        nx,ny = x+dx,y+dy
        if 0<=nx<n and 0<=ny<n:
            if arr[ny][nx] == '1' and c < visit[ny][nx]:
                visit[ny][nx] = c
                hq.heappush(heap,(c,nx,ny))
            elif arr[ny][nx] == '0' and c+1 < visit[ny][nx]:
                visit[ny][nx] = c+1
                hq.heappush(heap,(c+1,nx,ny))

 

코멘트

벽부수고 이동하기?