코딩테스트> 그래프 고급 탐색 ( 다익스트라, 크루스칼)

다익스트라

 

 

10282번 백준

아이디어

다익스트라로 시작점에서 모든 점의 최저 거리가 있는 배열을 만들고

지나가는 점과 가장 긴 거리를 골라서 출력

---

5719번 백준 

 

아이디어

최단 거리로 나온 결과값은 빼고 거기서 또 최단 거리를 뽑는다.

다익스트라 이중 처리

다익스트라를 점검할 때 이전에 적용이 되었는지 조건문에 추가

최단 거리를 다 구하면 최단 거리 값에서 역순으로 경로를 찾는다.

경로를 찾아가면서 이전에 적용됐다는 표시를 한다.

 

 

---

크루스칼

 

1774번 백준

 

아이디어

우주신인지 뭔지 복잡하게 씌여있지만 크루스칼 알고리즘을 사용하면된다.

이 문제의 특징은 이미 연결되어 있는 간선이 있다는 점이다.

그리고 기존은 간선이 있는 그래프를 정렬하여 사용했지만 

이번에는 모든 간선을 만들고 정렬하는 방법을 사용했다.