[BOJ]11403_경로찾기

경로찾기

풀이

플로이드-워셜 알고리즘

모든 정점에 대한 경로를 계산하는 알고리즘이다.

플로이드 와샬 알고리즘을 사용하여 어느 한 곳에 들려 다른 곳으로 가는 길이 존재한다면 그 값을 체킹해준다.

그리고 그 그래프를 출력하면 된다.

graph[a][k] == 1 and graph[k][b] == 1이면 a에서 b로 갈 수 있다라는 점이 핵심이다.

---

주의할 점이 한 가지있다.
자기 자신으로 가는 경로를 처리하는 과정에서 헷갈릴 수가 있다.
자기 자신으로 돌아오는(ex - 1에서 1로 가는) 직접적인 경로는 없다고 문제에 쓰여있다.
따라서 다른 노드를 통해서만 자기 자신에게 도착할 수 있고 이 또한 방문한 노드에 관한 정보를 담는 배열에 담긴다.

코드

import sys
sys.stdin =open('in.txt','rt')
input = sys.stdin.readline

n = int(input())
graph = [] 

for _ in range(n) : 
    graph.append(list(map(int,input().split())))

#플로이드워셜 알고리즘 
for k in range(n): # 모든 정점을 확인하기 위해 k 사용 
    for i in range(n):
        for j in range(n):
            if graph[i][k] and graph[k][j] : # 어느 한 곳에 들려 다른 곳으로 가는 길이 존재한다면 그 값을 체킹
                graph[i][j] = 1 

                
for i in graph : 
    for j in i : 
        print(j,end=' ')
    print()