📌문제
🎖️난이도
✔️풀이
# sol1) graph[i][i]도 못간다고 생각하고 무한으로 초기화 & 플로이드워셜로 최단거리 구하기
import sys
input = sys.stdin.readline
n = int(input())
INF = int(1e9)
graph = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
for j in range(n):
if graph[i][j] == 0: graph[i][j] = INF # 무한으로 초기화
for k in range(n):
for i in range(n):
for j in range(n):
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]) # 최단거리 get
for i in range(n):
for j in range(n):
if graph[i][j] in (0, INF):
print(0, end=' ')
else:
print(1, end=' ')
print()
# sol2) k를 거쳐서 갈 수 있으면 i->j는 일단 갈 수 있는 길이라고 1 표시 (플로이드워셜 응용)
import sys
input = sys.stdin.readline
n = int(input())
INF = int(1e9)
graph = [list(map(int, input().split())) for _ in range(n)]
for k in range(n):
for i in range(n):
for j in range(n):
if graph[i][k] and graph[k][j]: graph[i][j]=1 # 거쳐서 갈수있으면 1
for i in range(n):
for j in range(n):
print(graph[i][j], end=' ')
print()
'''
# Asterisk(*)를 이용한 출력(Unpacking)
for row in graph:
print(*row)
'''
🧠노트
all pairs 문제이므로 DP를 이용해서 플로이드-워셜 알고리즘으로 풀이하면 된다.
단, 여기서는 사실상 최단경로를 구하는 게 아니라
노드 i에서 노드 j로 갈 수 있는 경로가 있는지(0) 없는지(1)를 따지는 문제이므로
이를 주의해줘야 한다!
sol1)에서는 처음에 자기 자신으로 가는 비용(graph[i][i])을 0이 아니라 INF로 초기화 해주는게 포인트였고,
sol2)에서는 플로이드워셜 알고리즘을 응용해서, k를 거쳐서 가는 길이 존재하면 1로 바꿔주는 식으로 풀어준다.
플로이드 워셜이라고 모두 점화식(min)으로 값을 비교하며 최단거리를 구해야만 하는 건 아님!
🔍참고
[ Asterisk(*) 를 이용한 Unpacking ]
test = [1, 2, 3, 4, 5]
print(test) # [1, 2, 3, 4, 5]
print(*test) # 1 2 3 4 5
백준 같은 데에서 응용 가능!
(리스트에 저장된 값을 하나하나 공백으로 구분해서 출력해야 할 때)
'[ 알고리즘 ] > Shortest Path' 카테고리의 다른 글
[백준] 11404. 플로이드 (0) | 2022.07.19 |
---|---|
[백준] 1753. 최단경로 (0) | 2022.07.15 |
[백준] 18352. 특정 거리의 도시 찾기 (0) | 2022.07.15 |
[개념 정리] 최단 경로 (Shortest Path) 알고리즘 (2) | 2022.07.12 |