[백준/Python] 1261 알고스팟

문제링크

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

1261번: 알고스팟

---

코드

import sys
import heapq
input = sys.stdin.readline

def dijkstra(x,y):
    q = []
    distance[x][y] = 0
    heapq.heappush(q,(0,x,y))
    while q:
        dist,x,y = heapq.heappop(q)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx<0 or ny<0 or nx>=n or ny>=m:continue
            cost = dist + graph[nx][ny]
            if cost<distance[nx][ny]:
                distance[nx][ny] = cost
                heapq.heappush(q,(distance[nx][ny], nx,ny))
    return distance[-1][-1]
        
m,n = map(int,input().split())
INF = float('inf')
graph = [list(map(int,input().strip())) for _ in range(n)]
distance = [[INF]*(m) for _ in range(n)]
dx,dy = [-1,1,0,0], [0,0,-1,1]
print(dijkstra(0, 0))

---

 

문제풀이

기본적인 다익스트라 유형과 아주 유사하다. 기본적인 다익스트라 유형은 한 노드에서 갈 수 있는 노드들을 확인해보는 반면 이 문제는 상,하,좌,우를 확인한다. 그런 의미에서 graph[nx][ny]는 graph[x][y]에서 갈 수 있는 가중치가 된다. 따라서 graph[nx][ny]+dist가 distance[ny][ny]보다 작다면 ( 더 빨리 갈 수 있다면) 값을 갱신해주면 된다.

또한 bfs로도 풀 수 있는데 4방향을 검사하고 아직 방문하지 않았고 0(벽이 아니면) q의 앞에, 1(벽이면) q의 뒤에 append해주면 부셔야하는 최소한의 벽의 갯수를 구할 수 있다. 위 코드에서 다익스트라가 최소힙으로 동작하기 때문에 이와 같은 개념으로 볼 수 있다.