상세 컨텐츠

본문 제목

[Baekjoon Online Judge] 백준 11404번 플로이드(Python)

Problem Solving/Baekjoon Online Judge

by HelloMinchan 2020. 6. 12. 21:03

본문

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 11404번 플로이드

(Python)

(글쓴날 : 2020.06.12)

 


* Baekjoon Online Judge, 백준 11404번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.


 

 

백준 11404번 플로이드


1) 문제

문제 링크 : https://www.acmicpc.net/problem/11404

 

11404번: 플로이드

첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 �

www.acmicpc.net


2) 풀이 과정

* 시간 복잡도 : O(EV²)

 

n개의 도시와 각 도시별 버스 노선 금액이 주어질 때, 모든 도시의 쌍(A, B)에 대해 A에서 B로 가는데 필요한 최소 비용을 구하는 문제입니다.

단, 시작 도시와 도착 도시가 같은 경우는 없으며, 각 도시를 연결하는 노선이 하나가 아닐 수 있습니다.

 

저의 경우, 플로이드 와샬 알고리즘을 적용하였고, Python을 사용했습니다.

주어지는 정보 중 같은 경로가 주어질 시 최소 금액을 기록해야 하는 것을 고려하여 인접 행렬을 구현한 뒤, 플로이드 와샬 알고리즘을 적용해 모든 도시의 각 도시별 최소 비용을 구하여 문제를 해결했습니다.


3) 코드

 

* Python 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import sys
input = sys.stdin.readline
 
def floydWarshall():
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
 
= int(input())
= int(input())
INF = 2147483647
dist = [[0* n] + [[0+ [INF] * n for _ in range(n)]
 
for i in range(1,n+1):
    dist[i][i] = 0
 
for _ in range(m):
    a,b,c = map(int,input().split())
 
    dist[a][b] = min(dist[a][b], c)
 
floydWarshall()
 
for i in range(1,n+1):
    for j in range(1,n+1):
        print(dist[i][j] if dist[i][j]!=INF else 0, end=" ")
    print()

 

관련글 더보기

댓글 영역