[알고리즘] 백준 11403 파이썬 - 경로 찾기

 

11403번: 경로 찾기

문제

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

 

문제풀이

n=int(input())
graph=[]
for _ in range(n):
    graph.append(list(map(int,input().split())))
#01
for k in range(n):
    for i in range(n):
        for j in range(n):
        	#02
            if graph[i][k]==1 and graph[k][j]==1:
                graph[i][j]=1
#03
for i in graph:
    for j in i:
        print(j, end=" ")
    print()

- #01 : 플로이드-워셜 알고리즘을 사용하였고, 이는 모든 최단 경로를 구할 때 사용하는 알고리즘이다.

알고리즘 - 플로이드-워셜(Floyd-Warshall) 알고리즘

- #02 : 여기서 우리는 최단 경로를 구하는 것이 아니고. graph 상에 

           연결된 노드들을 표시하는 것이 목표이다.

           graph[i][k]와 graph[k][j]가 모두 1인, 즉 두 값이 연결될 때 해당 값을 1로 바꾸어준다.

- #03 : 모두 바꾼 graph 값을 i에 대입하고 i는 j에 대입한다.

           이후 j를 공백을 기준으로 출력한다. 이후 \n을 기준으로 한줄씩 나누어 출력한다.