[SWEA 5263][Python] [파이썬 S/W 문제해결 최적화] 4일차 - 그래프 최소 비용

코드

## SWEA 5263
T = int(input())
for test_case in range(1, T + 1):
    N = int(input())
    arry = [list(map(int, input().split())) for _ in range(N)]
    result = -float("inf")
    dist_arry = [[float("inf")]*N for _ in range(N) ]

    for i in range(N):
        for j in range(N):
            if arry[i][j] != 0 :
                dist_arry[i][j] = arry[i][j]

    for k in range(N):
        for i in range(N):
            if i!=k :
                for j in range(N):
                    if j!=k and j!=i :
                        dist_arry[i][j] = min( dist_arry[i][j], dist_arry[i][k]+dist_arry[k][j] )

    for i in range(N) :
        for j in range(N) :
            if dist_arry[i][j] != float("inf") and result < dist_arry[i][j] :
                result = dist_arry[i][j]

    print(f"#{test_case} {result}")

 

풀이

일반적인 그래프 최소 비용 산출 문제이다. 

완전탐색처럼 모든 노드를 탐색하되, 출발지 / 경유지 / 도착지 가 겹치지 않게 하여 출발지~도착지의 최소 거리를 2차원 list에 저장했다. 

비용이 음수인 경우가 있어서 result 값을 -Inf 로 초기화 했다. 

DP의 기초 개념?을 알려주고자 나온 문제인 것 같다.