[백준] 11403. 경로 찾기

 

📌문제

11403번: 경로 찾기

 

🎖️난이도

 

✔️풀이

# 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

백준 같은 데에서 응용 가능!

(리스트에 저장된 값을 하나하나 공백으로 구분해서 출력해야 할 때)