백준1261 - 알고스팟 (다익스트라) Python

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

해당 문제는 '벽을 부술 수 있는 미로'라는 점에서, 처음 접해보는 문제였다.

막힌 벽이 존재할 경우, 원하는 경로까지 갈 수 없기 때문에 일반적인 BFS 알고리즘으로는 접근이 불가능하다.

따라서, '부수는 벽'을 가중치로 하여 '최소 부순 벽'을 도출할 수 있게끔 다익스트라 알고리즘으로 접근했다.

 

풀이 과정은 다음과 같다.

 

1. 주어진 입력값을 분리시킨다.

def solution (data) :
  X, Y = map(int, data.pop(0).split())
  matrix = list(map(lambda x : list(map(int,list(x))) , data))

 

다익스트라 알고리즘 

2. 우선순위 큐(최소 힙)으로 사용할 배열 선언 후, 초깃값으로 (깨진 벽, x좌표, y좌표)를 삽입한다.

 

3. 좌표에 따라 부순 최소 벽의 갯수를 담을 Y * X 배열을 선언한 뒤, 모두 '무한대'로 초기화한다.

이때, 시작지점인 0,0 좌표는 부순 벽이 없으므로 0.

def dijkstra (matrix,X,Y) :
  # 2.
  pq = []
  heapq.heappush(pq, (0,0,0)) # 순서대로 (벽, x좌표, y좌표)
  matrix[0][0] = 0 # 문제에서 시작점이 벽이 아니라는 가정이 없어 추가한 내용
  # 3.
  dp = [[float('inf')] * X for _ in range(Y)]
  dp[0][0] = 0

 

4. 우선순위 큐에서 값을 빼낸다. (heapq 에 삽입된 인자 중 맨 앞에 위치한 인자인 '벽'이 우선순위가 가장 높음)

 

5. 이후 갈 수 있는 경로를 탐색하여 검증(verify 함수), 다음 경로가 방문한 적 없는 경우('무한대'인 경우)라면 해당 좌표에 '부순 벽'을 새로 메모라이징한다. (이때, 해당 좌표가 벽인 경우, '부순 벽 + 1'을 메모라이징)

 

6. 이후 다음 경로를 heap에 추가.

 

7. 종착점에 있는 값 리턴.

 

  while pq :
    # 4
    wall, x, y = heapq.heappop(pq)

    directions = [[-1,0], [1,0], [0,-1], [0,1]]
    for dx, dy in directions :
      nx, ny = dx + x, dy + y
      # 5
      if verify(nx,ny,X,Y) and dp[ny][nx] == float('inf') :
        temp = wall
        if dp[ny][nx] > wall :
          if matrix[ny][nx] == 1 :
            temp += 1
          dp[ny][nx] = temp
          # 6
          heapq.heappush(pq, (temp, nx, ny))
  # 7
  return dp[-1][-1]

# 올바른 좌표인지 검증하는 함수
def verify (x,y,X,Y) :
  return 0 <= x < X and 0 <= y < Y

 

 

전체 소스 코드

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()
import heapq

def solution (data) :
  X, Y = map(int, data.pop(0).split())
  matrix = list(map(lambda x : list(map(int,list(x))) , data))
  print(dijkstra(matrix, X,Y))
  
def dijkstra (matrix,X,Y) :
  pq = []
  heapq.heappush(pq, (0,0,0))
  matrix[0][0] = 0
  dp = [[float('inf')] * X for _ in range(Y)]
  dp[0][0] = 0
  
  while pq :
    wall, x, y = heapq.heappop(pq)
  
    directions = [[-1,0], [1,0], [0,-1], [0,1]]
    for dx, dy in directions :
      nx, ny = dx + x, dy + y
      if verify(nx,ny,X,Y) and dp[ny][nx] == float('inf') :
        temp = wall
        if dp[ny][nx] > wall :
          if matrix[ny][nx] == 1 :
            temp += 1
          dp[ny][nx] = temp
          heapq.heappush(pq, (temp, nx, ny))
    
  return dp[-1][-1]

def verify (x,y,X,Y) :
  return 0 <= x < X and 0 <= y < Y

solution(input_data)