백준 - 1504번(다익스트라, DP)

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

1504번: 특정한 최단 경로

import sys
import heapq

n,e = map(int,sys.stdin.readline().split())
arr = [[] for _ in range(n+1)]

for _ in range(e):
    a,b,c = map(int,sys.stdin.readline().split())
    arr[a].append([b,c])
    arr[b].append([a,c])

v1,v2 = map(int,sys.stdin.readline().split())

def dajik(s,e):
    if s == e:
        return 0

    q = []
    heapq.heappush(q, [0, s])
    dist = [float('inf')] * (n + 1)
    while q:
        now_value, s = heapq.heappop(q)
        for i in arr[s]:
            if now_value + i[1] < dist[i[0]]:
                dist[i[0]] = now_value + i[1]
                heapq.heappush(q, [now_value + i[1], i[0]])
    return dist[e]

p1 = dajik(1,v1) + dajik(v1,v2) + dajik(v2,n)
p2 = dajik(1,v2) + dajik(v2,v1) + dajik(v1,n)

ans = min(p1,p2)

if ans == float('inf'):
    print(-1)
else:
    print(ans)

엄밀히 말해서 DP문제는 아니지만 최적해를 구해서 합하는 개념이 DP문제에서 착안할 수 있기에 DP문제로 분류했다. DP맛 다익스트라 문제라고 볼 수 있다.

처음에는 단순하게 v1, v2 두 개를 방문하는 경우만 고려해서 둘 다 방문을 했을 때 n에 처음 도달하는 경우를 출력해 줬는데 이러면 메모리 초과가 났다. 그렇다면 방법은 부분으로 나눈 후 최적해를 구해서 더해 주는 것이 효율적이란 생각을 했다.

 

우선 특정 조건을 만족하면서 최단 거리를 찾아야 한다.

특정 조건은 간선에 방향이 존재하지 않고 v1,v2 간선을 무조건 방문해야 하는 것이다.

따라서 시작 지점 1에서 부터 시작해서 1 -> v1 -> v2 -> n or 1 -> v2 -> v1 -> n을 만족하는 최단 거리를 찾아 주면 된다.

이때 각 정점에서 정점까지의 거리를 dajik이라는 함수를 이용해서 찾아주면 된다. v1과 v2 둘 다 방문해야 하는 것이 자명하지만 무엇을 먼저 방문해야 이득인지는 해봐야 알기 때문에 위처럼 두 가지 case를 만들어 주는 것이다.

다익스트라 함수 자체는 새롭게 정점에 도달한 거리가 기존 값보다 작다면 교체해주는 것이다.

그렇게 해서 p1, p2의 최단 거리를 찾아주면 된다. 만약에 최솟값이 inf 일 경우 만족하는 경우가 없는 것이므로 예를 들어 p1이면 셋 중 하나라도 만족이 안될 경우 하나가 inf 가 돼버리기 때문에 무조건 inf가 된다.

유사한 문제로 BFS를 이용한 아기 상어가 있다. 이것도 특정 조건에 따라서 BFS를 나눈 후 최적해를 구해줘서 모두 더해줘야 하는 문제다.