11403

날짜 : 2022. 12. 06

사용 언어 : python

 

문제

 

 

코드

import sys

n = int(sys.stdin.readline())  # 정점의 개수
g = list()

for _ in range(n):
    g.append(list(map(int, sys.stdin.readline().split())))  # 그래프 입력

# 플로이드-워셜
for k in range(n):  # 중간경로가 가장 상위의 for문 (i -> k -> j)
    for i in range(n):
        for j in range(n):
            if g[i][j] == 1 or (g[i][k] == 1 and g[k][j] == 1):  # 가능한 경로가 있는 경우
                g[i][j] = 1  # i->k->j : a[i][k] + a[k][j]

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

 

 

풀이

- 플로이드-워셜 알고리즘을 활용하여 풀이한다.

- i -> j 로 가는 경로 중 직통이 없는 경우 다른 노드를 경유해서 도달한다.

- a[i][j] 가 i -> j로 가는 경로라고 할 때 만약 노드 k를 경유해서 도달할 수 있다면 a[i][j] = a[i][k] + a[k][j] 가 도출된다.

- 이를 활용하여 3중 for문을 사용, k를 이용해서 도달할 수 있는 조건을 이용해 그래프의 도달 가능여부를 체크한다.

(이 문제에서느 최소경로길이를 구하는 것은 논외로 취급한다.)

 

 

알게된 점

- 그래프에서 heqp, DFS, BFS만 사용하다가 새로운 알고리즘이 나와서 새로웠다.

 

 

참고 사이트

- https://claude-u.tistory.com/336

#285 백준 파이썬 [11403] 경로 찾기 - 플로이드 와샬

- 플로이드-워셜 알고리즘 : https://namu.wiki/w/플로이드-워셜%20알고리즘