|
import sys
input = sys.stdin.readline
import heapq
V = []
n= int(input())
for i in range(n) :
V.append(list(input()))
def cost(x) :
if x == '1' :
return 0
if x == '0' :
return 1
maxc = 2 * n
D = {}
for i in range(n) :
for j in range(n) :
D[(i, j)] = maxc
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def DIJK(start) :
D[start] = 0
heap = [[0, start]]
while heap :
c, q = heapq.heappop(heap)
if c <= D[q] :
for i in range(4) :
x = q[0] + dx[i]
y = q[1] + dy[i]
if x < 0 or y < 0 or x >= n or y >= n :
continue
if c + cost(V[x][y]) < D[(x, y)] :
D[(x, y)] = c + cost(V[x][y])
heapq.heappush(heap, [c + cost(V[x][y]), (x, y)])
DIJK((0, 0))
print(D[(n-1, n-1)])
|
갈 수 있는 곳(흰색)과 없는 곳(검은색)으로 접근하여 BFS를 쓰려 하면 풀이가 떠오르지 않는다.
벽을 부수는 것을 비용으로 봄으로써 비용 0으로 갈 수 있는 곳(흰색)과 1의 비용을 쓰면 갈 수 있는 곳(검은색)의 접근이 가능하다.
이렇게 접근하면 모든 인접한 블록은 연결되어있고 흰색은 비용 0, 검은색은 비용 1인 간단한 그래프가 된다.
비용(=벽을 부순 횟수)를 기록한 D를 만들고 다익스트라를 실행시킨 뒤 끝점의 D를 출력한다.
'Week 01 ~ 04 : 알고리즘 문제 풀이' 카테고리의 다른 글
| 파이썬 백준 3055 탈출 (0) | 2021.11.20 |
|---|---|
| 파이썬 백준 7569 토마토 (0) | 2021.11.20 |
| 파이썬 백준 1916 최소비용 구하기 (0) | 2021.11.20 |
| 파이썬 백준 18352 특정 거리의 도시 찾기 (0) | 2021.11.20 |
| 파이썬 백준 2718 미로 탐색 (0) | 2021.11.20 |