11403번. 경로 찾기

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

 

 

DFS로도 풀 수 있지만, 플로이드-워셜 알고리즘으로 풀리는 문제.

플로이드 워셜 알고리즘이란 

정점 i 에서 정점 j 로 가는 경로가 있는지 확인하고 싶을 때,

 

i 에서 j 로 가는 직통 길이 있니? matrix[i][j] == 1? 

k ( k = 모든 정점 ) 를 지나쳐 가는 길이 있니? matrix[i][k] == 1 and matrix[k][j] == 1?

 

를 확인하는 알고리즘. k에는 0부터 마지막 정점까지 모든 정점을 하나씩 대입한다.

플로이드 워셜 알고리즘에서는 최단 거리를 발견할 때마다 업데이트하지만

여기서는 최단 거리가 아니라 가는 경로 유무 1, 0으로 만 확인하면 된다.