[백준] 11403번 : 경로 찾기 (Python)

문제: https://www.acmicpc.net/problem/11403

 

import sys

input = sys.stdin.readline

V = int(input()) # 정점의 개수

matrix = [[0 for _ in range(V+1)]] # 인접 행렬
    
# 인접 행렬을 matrix 행렬에 저장
for i in range(V):
    matrix.append([0] + list(map(int, input().split())))

# 플로이드-워셜 알고리즘 수행
for k in range(1, V+1):
    for i in range(1, V+1):
        for j in range(1, V+1):

            if(matrix[i][k]+matrix[k][j] > 1): # 경로가 존재 시
                matrix[i][j] = 1 # 존재 여부 표시
            
# 경로 print
for i in range(1, V+1):
    for j in range(1, V+1):
            print(matrix[i][j], end=' ')
    print()

 

 

[문제풀이]

---

모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 구해야 한다.

즉, 플로이드-워셜 알고리즘을 사용해서 경로가 있는지 확인해야 함!

 

경로 여부는 이를 통해 구한다.

if(matrix[i][k]+matrix[k][j] > 1): # 경로가 존재 시
    matrix[i][j] = 1 # 존재 여부 표시

 

인접행렬에는 i에서 j로 가는 경로가 있을 시 1이 저장된다.

matrix[i][k], matrix[k][j] 둘 모두 1이면 k를 거쳐 i에서 j로 가는 경로가 있단 의미이며, 그럼 이 경로가 존재한다고 표시!

 

이렇게 모든 경로 여부를 구할 수 있다.