BOJ/11403_경로 찾기

[문제]

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

[처음 생각]

가중치가 없는 방향 그래프인 것을 생각했을 때, 

i에서 j로 가는 경로에는 첫번째로 i에서 바로 j로 가는 방법과 두번째로 i에서 임의의 점 k를 거쳐서 j로 가는 방법이 있다. 

그래서 처음에는 2차원 행렬일때의 BFS 사용법(상하좌우 움직이여가며 방문 노드 체크)을 해봤지만, 이렇게 했을 때는 단순히 직접 연결된 경로밖에 찾지 못한다. 

그 다음으로 생각한 방법은 인접 행렬을 인접 리스트로 바꾸는 방법을 생각했고 (-> 인접 리스트 작성법을 몰라서 스킵...)

입력 받은 인접 행렬을 검사하면서 간선이 존재하면 그 j값을 다시 시작점 i값으로 봐서 거기서 다시 연결된 점들을 찾고 그 점들을 연결 리스트처럼 생각해서 연결된 경로를 체크하는 것이다. (-> 근데 이렇게 하면 나열된 연결 리스트같은 점들 안에서 다시 여러 경로를 찾아야 하므로 복잡할 것 같음)

[풀이]

★헷갈리지 말아야 할 것!!!

i에서 j로 갈 때 중간 경로 k를 거친다는 것이 i에서 k로 가는 경로가 직진 경로가 아닐수도 있다는 점이다.

i에서 k로 가는 경로 또한 중간 경로가 존재할수도 있고 계속 경로를 쪼개서 생각하면 된다.

여기서는 플로이드-워셜 알고리즘 사용이 BFS보다 편하다.

(중간 경로를 껴가면서 체크하므로 미리 계산된 작은 경로 문제의 결과를 이용하므로 플로이드-워셜 알고리즘을 사용하는 것이 좋다 -> DP)

중간 경로 k를 끼워 넣으며 전체 행렬을 검사하면 된다. 

arr[i][k] && arr[k][j]가 true라면 arr[i][j] 는 1이다. 

[참고]

http://gnujoow.github.io/boj/2016/09/08/BOJ5-11403

[Code]

https://github.com/dbwls94/gomulsang/blob/youjin/BOJ/src/boj_11403/FindRoute.java

--> 원래는 제대로 플로이드-워셜 알고리즘을 사용했다면 바로 직결되는 경로와 중간 경유지를 거치는 경로 중에서 최솟값을 가지는 경로를 선택해야 한다. (최단 경로를 찾는 알고리즘이므로)