1263. [S/W 문제해결 응용] 8일차 - 사람 네트워크2 (python)

문제 URL : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18P2B6Iu8CFAZN&categoryId=AV18P2B6Iu8CFAZN&categoryType=CODE&problemTitle=%EC%9D%91%EC%9A%A9&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

문제 접근법:

이런종류 문제 많이풀어서

그냥 공식대로 그냥 풀어볼 까 생각했는데

트리가 아니라 그래프더군요

트리라면 공식이 존재하지만 그래프라 크루스칼 알고리즘을 썼는데

그냥 되더군요 솔직히 시간이 이렇게 길게 나올줄알고 안쓰다가 그냥 한번 써봐야지 했는데 된거라

시간을 줄이는 연습인 문제가 아니더군요

 

소스코드:

from collections import defaultdict
#import sys
#sys.stdin = open("input.txt","r")
Test = int(input())
for test in range(1,Test+1):

    t = list(map(int,input().split()))
    n = t.pop(0)
    l = [[0]*n for i in range(n)]
    for i in range(n):
        for j in range(n):
            l[i][j]=t[i*n+j]
            if i!=j and l[i][j]==0:
                l[i][j]=int(1e9)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                l[i][j]=min(l[i][j],l[i][k]+l[k][j])
    res = int(1e9)
    for i in range(n):
        sum = 0
        for j in range(n):
            if l[i][j]!=int(1e9):
                sum+=l[i][j]
        res = min(res,sum)
    print('#{} {}'.format(test,res))

 

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.