문제
접근
특정 노드 a, b 가 있을 때, a와 b가 연결되어 있는지 확인하는 문제이다.
이 때 a, b가 바로 연결되어 있다면 문제가 없겠지만, (a, k), (k, b)로 중간 노드를 거치는 경우를 어떻게 해결할지가 관건이다.
나는 모든 노드 k에 대해 반복문을 돌며 k를 중간 지점으로 가지는 노드들에 대해 확인해주었다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n = int(input())
arr = []
for i in range(n):
tmp = [int(i) for i in input().split()]
arr.append(tmp)
for k in range(n):
for i in range(n):
for j in range(n):
if arr[i][k] and arr[k][j]:
arr[i][j] = 1
for i in range(n):
for j in range(n):
print(arr[i][j], end = ' ')
print()