[백준 파이썬] 1261 알고스팟

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

1261번: 알고스팟

문제

해당 지점으로 이동할 때 가장 적게 벽을 부수는 경우를 구하는 문제이다

---

 

아이디어

최단거리를 탐색하는 문제이기 때문에 다익스트라를 이용하였다.

---

풀이

def dijkstra():
  q = []
  heapq.heappush(q, (0, 0, 0)) #cost, x, y
  distance[0][0] = 0

  while q:
    cost, x, y = heapq.heappop(q)
    if cost > distance[y][x]:
      continue

    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if 0 > nx or nx >= N or 0 > ny or ny >= M:
        continue


      if cost + graph[ny][nx] < distance[ny][nx]:
        distance[ny][nx] = cost + graph[ny][nx]
        heapq.heappush(q, (distance[ny][nx], nx, ny))

 

다익스트라의 구현은 위와같다.

x, y, cost를 우선순위큐에 입력 후 자기자신의 거리를 0으로 초기화시킨다.

이 후 순회하며 새로운 거리값이 작을경우 큐에 넣어줌으로 써 최단거리를 갱신하였다.

 

---

코드

import sys
import heapq

N, M = map(int, input().split())

graph = [list(map(int, input())) for _ in range(M)]
distance = list([sys.maxsize] * N for _ in range(M))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dijkstra():
  q = []
  heapq.heappush(q, (0, 0, 0)) #cost, x, y
  distance[0][0] = 0

  while q:
    cost, x, y = heapq.heappop(q)
    if cost > distance[y][x]:
      continue

    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if 0 > nx or nx >= N or 0 > ny or ny >= M:
        continue


      if cost + graph[ny][nx] < distance[ny][nx]:
        distance[ny][nx] = cost + graph[ny][nx]
        heapq.heappush(q, (distance[ny][nx], nx, ny))

dijkstra()
print(distance[M-1][N-1])