그래프 최단경로 알고리즘 중 하나인 플로이드-와샬 알고리즘입니다.
이번 문제에서는 최단거리를 찾는 것이 아니라 통행이 가능하기만 하면 되기때문에
해당 노드들이 연결되어있는지까지만 찾아주었습니다.
연결된 노드인지 확인하는 방법은
라고 했을 때, graph[i][j] 가 1이거나 graph[i][k] 와 graph[k][j] 모두 1인 경우에 두 노드가 연결되어 있다는 것을 알 수 있습니다.
따라서 3중 반복문을 활용해 노드들의 연결성을 계산합니다.
for (int k = 0; k < N; ++k)
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
if ((graph[i][k] && graph[k][j]) || graph[i][j])
graph[i][j] = 1;
연결되어있다면 해당 노드도 1로 바꾸어 줍니다.