99클럽 코테 스터디 0일차 TIL (floyd-warshall)

🔗 Problem Link

https://www.acmicpc.net/problem/11403

---

❔Thinking

• 연결 여부를 나타내는 인접행렬이 주어질 때, 모든 정점의 연결 상태를 출력해야 한다.
• 정점의 개수가 100개 이하의 자연수이기 때문에, 플로이드-워셜 알고리즘도 활용 가능하다.
• 최단 거리를 구하는게 아니라 연결 여부만을 판단해 가능하다면 1, 아니라면 0으로 업데이트한다.

---

💻Solution

import sys
input = sys.stdin.readline

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

for k in range(N):
    for i in range(N):
        for j in range(N):
            board[i][j] = 1 if (board[i][k] == 1 and board[k][j] == 1) else board[i][j]
            
for b in board:
    print(*b)

---

🗝️keypoint

• K의 범위에 따라 모든 경로를 확인하기 때문에, 각 정점의 연결상태를 구할 수 있다.
• for문으로 board의 각 행을 출력할경우, unpack이나 join을 통해 출력 형식을 맞춰야 한다.