[Python] 백준/BOJ 11403번: 경로 찾기 (Silver 1)

💻 Problem

문제 보러 가기

 

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

 

💡 Approach

아래는 백준 예제 입력을 기반으로 그린 그래프의 모습이다.

그림으로 보면 각 노드가 어떻게 이어져있는지 더 쉽게 이해할 수 있다.

예제 그래프

 

플로이드 워셜 알고리즘으로 풀었다.

플로이드 워셜의 키워드는 경출도!!

3중 for문을 경유지-출발지-도착지 순으로 적어야 한다.

 

처음 입력받은 인접 행렬에는 직접적으로 이어지는 간선이 존재하는지 저장되어 있다.

이 인접 행렬에서 간접적으로 이어지는지(경유지를 통해)를 업데이트하면 그게 정답이다.

 

출발지와 경유지가 이어져있고 경유지와 도착지가 이어져있으면 출발지에서 도착지로 이동할 수 있다.

그러니 출발지에서 도착지까지도 이동할 수 있다고 인접 행렬에 업데이트해준다.

 

✏️ Solution

import sys
input = sys.stdin.readline

n = int(input())
adj = [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 adj[i][k] and adj[k][j]:
                adj[i][j] = 1

for row in adj:
    print(*row)

시간복잡도: O(n^3)