백준 11404번 / 이코테 수록

문제

• 입력
  • 첫째줄에 도시의 개수 n
    • 1<=n<=100
  • 둘째 줄에는 버스의 개수 m
    • 1<=m<=100,000
  • 셋째줄부터 버스의 정보 a(시작도시), b(도착도시), c(비용. 1<=c<=100,000)
• 출력
  • n개의 줄을 출력하되,
  • i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는 데 필요한 최소 비용. 만약 i에서 j로 갈 수 없는 경우에는 그자리에 - 출력

풀이

처음 보고 든 생각

플로이드 워셜로 모든 점에서의 모든 점으로의 최소 비용을 구해야겠다

풀이 아이디어

플로이드 워셜이되, A와 B를 잇는 간선이 여러개일 수 있다.
➡️ 가장 짧은 간선 정보만 저장한다.

시간복잡도

플로이드 워셜의 시간복잡도는 o(N^3)

코드

INF = int(1e9)

# 노드의 갯수 및 간선 갯수 입력받기
n = int(input())
m = int(input())
# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n+1) for _ in range (n+1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n+1) :
	for b in range(1, n+1) :
		if a == b :
			graph[a][b] = 0

# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(m) :
	# A에서 B로 가는 비용은 C라고 설정
	a, b, c = map(int, input().split())
	# 가장 짧은 간선 정보만 저장 #### 중복 간선은 최솟값만 저장한다!!! ####
	if c < graph[a][b] :
		graph[a][b] = c

# 점화식에 따라 플로이드워셜 알고리즘을 수행
for k in range(1, n+1) :
	for a in range(1, n+1) :
		for b in range(1, n+1) :
			graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 수행된 결과 출력
for a in range(1, n+1) :
	for b in range(1, n+1) :
		# 도달할 수 없는 경우, 0 출력
		if graph[a][b] = INF :
			print(0, end=" ")
		else :
			print(graph[a][b], end=" ")
	print()

느낀점

플로이드 워셜 거의 그대로다!
중복간선은 최솟값만 저장하는것만 달랐다.