[백준 파이썬] 2665 미로만들기

 

2665번: 미로만들기

문제

해당 지점으로 이동할 때 가장 적은 수로 방을 바꾸는 문제이다.

---

 

아이디어

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

---

풀이

def dijkstra():
  q = []
  heapq.heappush(q, (0, 0, 0))
  distance[0][0] = 0

  while q:
    cost, x, y = heapq.heappop(q)

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

      if 0 <= nx < n and 0 <= ny < n and distance[ny][nx] > cost + 1:
        if graph[ny][nx] == 0:
          distance[ny][nx] = min(distance[ny][nx], cost + 1)
        else:
          distance[ny][nx]= min(distance[ny][nx], cost)
        heapq.heappush(q, (distance[ny][nx], nx, ny))

 

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

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

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

놀랍게도 알고스팟 문제와 정확히 동일하게 해결하였다.

 

---

코드

import sys
import heapq

n = int(input())

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

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

def dijkstra():
  q = []
  heapq.heappush(q, (0, 0, 0))
  distance[0][0] = 0

  while q:
    cost, x, y = heapq.heappop(q)

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

      if 0 <= nx < n and 0 <= ny < n and distance[ny][nx] > cost + 1:
        if graph[ny][nx] == 0:
          distance[ny][nx] = min(distance[ny][nx], cost + 1)
        else:
          distance[ny][nx]= min(distance[ny][nx], cost)
        heapq.heappush(q, (distance[ny][nx], nx, ny))

dijkstra()
print(distance[n-1][n-1])