[Python] SW Expert Academy #1263 사람 네트워크2

📚문제: #1263 사람 네트워크2(D6)

전체 코드

# 1263. 사람 네트워크2

# 플로이드-워셜 함수
def fw(G, n, t):
    
    INF = int(1e10)
    
    # 초기화
    for i in range(n):
        
        for j in range(n):
            
            # 같을 때는 0으로 초기화
            if i == j:
                
                continue
            
            elif G[i][j] == 0:
                
                G[i][j] = INF
                
    # logic
    for i in range(n):
        
        for j in range(n):
            
            for k in range(n):
                
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])
    
    min_sum = int(1e10)
    
    for i in range(n):
        
        min_sum = min(min_sum, sum(G[i]))
        
    # 답안 출력
    print("#{} {}".format(t, min_sum))
                
# 테스트 케이스 T
T = int(input())

# T개의 테스트 케이스
for t in range(1, T+1):
    
    # 사람 수 N과 인접 행렬이 주어진다.
    seq = list(map(int, input().split()))
    
    # 사람 수 N
    N = seq[0]
    del seq[0]
    
    # 인접행렬
    adj_mtx = []
    
    for i in range(N):
        
        temp = seq[i*N : i*N + N]
        
        adj_mtx.append(temp)
    
    # 함수 실행
    fw(adj_mtx, N, t)

아이디어

Floyd-Warshall 알고리즘 적용