[백준1162&파이썬] 다익스트라에서 distance를 여러가지로 갈래로 분리시켜야 할때

# 문제

백준 1162 도로포장 파이썬 풀이

1162번: 도로포장

 

# 코드

import sys
from collections import defaultdict
from heapq import *

# N : 도시의 수, M : 도로의 수, K : 포장할 도로의 수
N, M, K = map(int,sys.stdin.readline().split())
graph = defaultdict(list)


for _ in range(M) :
  a,b,w = map(int,sys.stdin.readline().split())
  # 무방향 도로
  graph[a].append((b,w))
  graph[b].append((a,w))

# 길을 까는것과 안까는 걸로 계속 나눠가는 형식으로 해보자
distance = [[float('inf')] * (N+1) for _ in range(K+1)] # 도로를 깔 수 있는 만큼
for i in range(K+1) :
  distance[i][1] = 0 # 초기 설정

heap = list()
heappush(heap, (0, 1, K)) # ( sum_weight, vertex, 현재 포장가능한 도로의 수 )

while len(heap) != 0 :
  cur = heappop(heap) # # ( sum_weight, vertex, 현재 포장가능한 도로의 수 )

  if distance[cur[2]][cur[1]] < cur[0] :
    continue

  for next in graph[cur[1]] : # ( vertex, weight )
    cost = distance[cur[2]][cur[1]] + next[1] # 도로를 깔지 않을때
    if cost < distance[cur[2]][next[0]] :
      distance[cur[2]][next[0]] = cost
      heappush(heap,(cost,next[0],cur[2]))

    if cur[2] > 0 : # 도로를 깔 수 있을 때
      cost = distance[cur[2]][cur[1]] + 0 # 0을 더해서 다음경로까지가 완성 됨
      if cost < distance[cur[2]-1][next[0]] :
        distance[cur[2]-1][next[0]] = cost
        heappush(heap,(cost,next[0],cur[2]-1))

mmin = float('inf')
for i in range(K+1) :
  mmin = min(mmin,distance[i][N])
print(mmin)

 

# 풀이

• BFS로 N까지 도착하는 모든 경우의수의 경로값들을 저장하고, 해당 경로에서 K만큼 큰수를 하나씩 지워나간 후, 그 값중에서 가장 작은 값을 찾으려 했지만, 메모리초과가 발생했다. 풀면서도 이 풀이는 아닐거라고 생각했다. 
• BFS문제중 벽부수고 이동하기라는 문제가 있는데 해당문제와 접근방법이 매우 유사했다. 그건 BFS라면 이건 다익스트라로 같은 접근을 하면 됐다.
• 도로를 K개 만큼 깔 수 있으며, 계속 상태가 분리돼 나가야한다. 이말은 즉, 현재 노드에서 다음 노드를 방문하여 distance값을 업데이트 할때, 하나는 도로를 깔지 않고 방문하고, 다른 하나는 도로를 깔아 방문한다. 이렇게 하게 되면 도로를 깔 수 있는지 먼저 확인하고, 가능하다면 현재정점에서 최단거리를 그대로 이전해준다. 
• 이러한 문제의 핵심은 방문처리를 어떻게 하느냐가 가장 큰 해결방법인거 같다. 최단거리값을 계속 업데이트하는 distance를 K개만큼 만들어 관리한다. 이말은 즉, distance[K]에 접근하면, 깔수 있는 도로가 K개 만큼 남았다는 말이고, 도로를 그만큼 사용했을때의 최단거리가 나타나게 된다.

 

# 참고

[백준2206&파이썬] BFS에서 이동상태가 분리된다면 방문 확인도 분리시켜야 한다.