[알고리즘][Python] 백준 11403 경로 찾기 문제 풀이

문제 출처 : www.acmicpc.net/problem/11403

11403번: 경로 찾기

---

문제 해석 : 이동 가능한지 여부를 경로를 토대로 구하는 문제이다. 몇번을 어디를 거쳐가는 지는 생각하지 않고 어떤 방식으로든 갈 수 있으면 1 없으면 0을 출력하면 된다.

 

문제 풀이 :  플루이드 - 워셜 알고리즘을 통해서 해결 가능하다. 플루이드 - 워셜 알고리즘은 거쳐가는 모든 경우를 고려하여 가능한지 검사 할 수 있다. 

---

풀이 코드

import sys
input = sys.stdin.readline

N = int(input())
visited = [list(map(int, input().split())) for _ in range(N)]

for k in range(N):
    for a in range(N):
        for b in range(N):
            visited[a][b] = max(visited[a][b], visited[a][k]&visited[k][b])

for i in range(N):
    for j in range(N):
        print(visited[i][j], end=" ")
    print()

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.