[탐색/플로이드] 백준 11403 경로 찾기 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

11403번: 경로 찾기

 

 

 

2. 문제 풀이

 인접리스트가 주어졌을 때, 경유지를 통해 갈 수 있는 경로가 있는지를 구하는 문제입니다.

 

2022.02.28 - [Algorithm] - [Algorithm] 플로이드-와샬, 모든 쌍의 최적경로 구하기

[Algorithm] 플로이드-와샬, 모든 쌍의 최적경로 구하기

 플로이드 와샬 알고리즘을 이용하면 쉽게 구할 수 있습니다. 플로이드 와샬 알고리즘은 모든 쌍의 최적 경로를 구하는 문제입니다. 이 문제는 단순히, 경로가 있는지만 구하면 됩니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

#플로이드 와샬 알고리즘
def floyd(n, dist):
    # 최단 경로 리스트 초기화
    for via in range(n): #경유지
        for start in range(n): #출발지
            for end in range(n): #도착지
                # 경유해서 가는 게 있다면, 경로 있음으로 교체
                if dist[start][via] * dist[via][end]:
                    dist[start][end] = 1
    return dist

 플로이드 와샬 알고리즘은 경유지가 더 빠르다면 경유지의 가중치로 교체합니다.

 하지만, 이 문제는 최적 경로를 구하는 문제가 아닙니다. 단순히 경유 경로가 있는지만 체크해서, 있다면 1로 바꿉니다.

 

 

#입력
N = int(input())
graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))

#플로이드 와샬
dist = floyd(N, graph)

#출력
for i in range(N):
    for j in range(N):
        print(dist[i][j], end=" ")
    print()

 그래프를 입력받고, 플로이드 와샬 알고리즘을 응용해서 경로를 찾아줍니다.