이거 테스트 케이스 답 얼마 나오나요?

눈으로만 봤지만 1-a-b-c가 연결되었을 때 1-c가 연결된 것으로 체크되지 않을겁니다.

1에서 시작하는 것만 체크하지 말고 일반적인 플로이드처럼 모든 정점에 대해서 구해야합니다.

( 플로이드 내부에서 그 값을 또 사용합니다. )

답이 3은 아닌 거 같죠?

왜 잘못된 값이 나오는지 시뮬레이션 돌려 봅시다.

아마 저대로 floyd 알고리즘을 수행해 버리면 어떻게 될 거냐면

지금 k가 1루프를 돌 때 마다 1 -> k로 가는 경로와 k -> j로 가는 경로가 있는지를 check 하고 있는데..

k = 2인 경우? 1->2와 2->j로 가는 경로가 동시에 존재하는 경우가 j = 4인 경우이므로 1->4로 가는 경로가 있다고 업뎃 되네요.

k = 3인 경우? 잘 될 지 의문이에요. 일단 이 때 임의의 k에 대해서 1->3와 3->j으로 가는 경로가 동시에 존재하는 경우가 없으므로, No.

k = 4인 경우? 1->4와 4->j로 가는 경로가 동시에 존재하는 경우가 j = 3인 경우인가요? 일단 1->4로 가는 경로는 무조건 존재하고요. 4에서 3으로 가는 경로 있으니까

1에서 3으로 가는 경로 또한 있다고 업뎃 될 거에요.

k = 5인 경우? 1->5와 5->j로 가는 경로가 동시에 존재하는 경우가 있냐고 물어보는데..

네. 없네요. 따라서 5는 갈 수 있음에도 못 간다고 표시하네요.

감사합니다.
모든 정점이 시작점의 역할을 해서 연결되는 정보를 업댓해야지 나중에 1과 연결되는지
최종적으로 판단이 되는군요 .. 고쳐서 맞았습니다.