Coding 공부

import sys
import heapq
input = sys.stdin.readline


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



graph = [{} for _ in range(N+1)]
INF = float('inf')
for _ in range(M):
    x,y,pay = map(int,input().split())
    graph[x][y] = min(graph[x].get(y,INF),pay)
    graph[y][x] = min(graph[y].get(x,INF),pay)


conquer = -1
pay_list = [[INF for _ in range(N+1)] for _ in range(2)]
pay_list[0][1] = 0
visted = [False]*(N+1)
cur_pay,cur_node = 0,1
result = 0
total_city = set(range(1,N+1))
while conquer<N-1:
    if visted[cur_node]:
        continue
    visted[cur_node] = True
    result += cur_pay
    total_city.remove(cur_node)
    conquer += 1
    idx = conquer%2
    if conquer > 0:
        prev_idx = (conquer+1)%2
        for city_num in total_city:
            pay_list[idx][city_num] = pay_list[prev_idx][city_num]+T
    
    min_idx = -1
    min_pay = INF
    for next_node in graph[cur_node]:
        temp_pay = graph[cur_node][next_node] + conquer*T
        if pay_list[idx][next_node] > temp_pay:
            pay_list[idx][next_node] = temp_pay

    for city_num in total_city:
        if min_pay > pay_list[idx][city_num]:
            min_pay = pay_list[idx][city_num]
            min_idx = city_num
    cur_pay,cur_node = min_pay,min_idx


print(result)

 이 문제는 어렵게 생각해서 오래 걸렸던 문제였다. 이 문제를 쉽게 생각해보면, conquer 비용은 고정적이다.

이 conquer 비용을 생각지 않고, 가장 마지막까지 구하고 난뒤에 conquer 비용만 더해주면 되는 문제이긴했다.

하지만 풀때에는 이 방식에 대해 잘 몰랐고, 그걸 적용시키지 않고, conquer 비용을 바로바로 구해주었다.

이 풀이의 방식은 다음과 같다 pay_list를 2*(N+1)로 해주었다.

즉 우리가 프림알고리즘에서 pay를 저장하는걸 1차원 배열 하나로 했던 거에 비해 2차원 배열을 이용해서 문제를 풀었다.

각각의 의미는 다음과 같다. 현재의 conquer 수치를 같이 저장을 해주면서

현재 conquer가 짝수이면, 0이고, 그때의 이전 pay_list 비용은 1번 인덱스에 있다.

현재 conquer가 홀수이면 1이고, 그때의 이전 pay_list 비용은 0번 인덱스에 있다.

즉 슬라이딩 윈도우처럼 각 전단계의 pay_list를 가져와서 현재 우리가 구하고자 하는

pay_list에 덮어씌워주는 방식으로 했다.

그 뒤에는 일반적인 프림알고리즘과 비슷하다.

현재 노드에서 갱신될수 있는것들을 전부 갱신을 한뒤에

모든 도시들을 찾아다니면서 가장 작은 값을 구해주면 되는 것이다.

import sys
import heapq
input = sys.stdin.readline


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



graph = [{} for _ in range(N+1)]
INF = float('inf')
for _ in range(M):
    x,y,pay = map(int,input().split())
    graph[x][y] = min(graph[x].get(y,INF),pay)
    graph[y][x] = min(graph[y].get(x,INF),pay)



pay_list =[INF for _ in range(N+1)]
node_list = []
visited = [False]*(N+1)
heapq.heappush(node_list,(0,1))
pay_list[1] = 0
result = 0
while node_list:
    cur_pay,cur_node = heapq.heappop(node_list)
    if pay_list[cur_node] < cur_pay or visited[cur_node]:
        continue
    visited[cur_node] = True
    result += cur_pay
    for next_node in graph[cur_node]:
        if pay_list[next_node] > graph[cur_node][next_node] and not visited[next_node]:
            pay_list[next_node] = graph[cur_node][next_node]
            heapq.heappush(node_list,(pay_list[next_node],next_node))


conquer_pay = (N-2)*(T+(N-2)*T)//2
result += conquer_pay
print(result)

이 풀이는 위에서 말한것처럼 어차피 conquer는 등차수열로 균등하게 증가하기 때문에, conquer를 배제하고,

우리가 일반적으로 구하는 프림알고리즘을 이용해서 문제를 해결한다.

그리고 난뒤에 등차수열의 합의 공식을 이용해서, conquer_pay를 구한뒤 결과값에 더해주면 된다.