[#알고리즘/최단 경로/[백준]11403번: 경로 찾기(python)]

Question

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

Solution

처음엔 DFS나 BFS로 푸는 방법을 생각했지만, 플로이드 워셜 알고리즘을 통해 간단히 풀 수 있다는 사실을 깨달았다. 처음 입력 예시를 생각해보자.

예제 입력1
3
0 1 0
0 0 1
1 0 0

위 정보를 그래프로 표현하면 아래와 같다.

문제에서 노드 i에서 j로 가는 경로가 있으면 1을 출력하라고 하였다. 여기서 우리는 입력 받은 경로에 추가로 한 가지 사실만 확인하면 된다. i에서 j로 직접 가지는 못하지만, i에서 k를 거쳐 j로 가는 경로가 있으면 결국 i에서 j로 가는 경로가 있는 것이 된다. 이는 앞서 배운 플로이드 워셜 알고리즘을 통해 쉽게 확인할 수 있다.

Code

import sys

input = sys.stdin.readline

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

# 각 간선에 대한 정보 입력받기
graph = []
for _ in range(n) :
    graph.append(list(map(int, input().split())))
        
# 플로이드 워셜 알고리즘 수행
for k in range(n) :
    for a in range(n) :
        for b in range(n) :
            if graph[a][k] and graph[k][b] :
                graph[a][b] = 1
            
# 결과 출력
for a in range(n) :
    for b in range(n) :
        print(graph[a][b], end=" ")
    print()