[Python] 이것이 코딩테스트다 9장 최단 경로

최단 경로의 핵심

최단 경로 알고리즘에는 다양한 종류가 있음.

 

우선 ,

 

• 한 지점에서 특정 지점으로 까지의 최단 경로를 구해야하는 경우
• 모든 지점에서 모든 지점까지의 최단 경로를 구해야 하는 경우

경우를 생각해본다.

 

또, 

 

• 최단 경로의 합을 구하는 경우
• 최단 경로에서 거쳐온 노드들을 구하는 경우

 

를 캐치 한다. 

 

🔑 앞서 공부한 그리디, 다이나믹은 최단경로 알고리즘에서 그래도 적용 된다.

 

 

• 다익스트라 알고리즘: 기준 노드에서 각 노드에 대한 현재까지의 최단 거리 정보를 항상 1차원 리스트에 저장하여 갱신한다는 특징이 있다. 
  
  방법 1. 구현하기 쉽지만 느리게 동작하는 다익스트라 O(n^2)
  방법 2. 구현하기 조금 어렵지만 빠르게 동작하는 다익스트라 (우선순위 힙 이용) O(elogv)

• 플로이드 알고리즘 : 2차월 리스트를 이용하여 모든 지점에서 다른 모든 지점까지로의 최단 거리를 구할 때 사용하는 알고리즘. O(n^3)

 

 

다익스트라는 방법1, 방법2 말하면 바로 나올 정도로 외워나야 한다. 

 

 

 

----------------------------------시간제한 참고

파이썬 => 1초 20000000번 연산

 

데이터 20,000,000 => O(N)

데이터 1,000,000 => O(NlogN)

데이터 4~5,000 => O(N^2)

데이터 100~200 => O(N^3)

---

다익스트라 예제

 

📝 체감난이도 : ★★☆☆☆☆

 

 

 

🎨 방법 1. 간단한 다익스트라

 

 

 

 

🎨 방법 2. 개선된 다익스트라

 

 

 

 

 

 

 

 

🔑 Key Point 

 

우선순위 힙을 이용하면 방문 여부의 노드를 만들 필요가 없고, 이미 정렬이 되어있기 때문에 '방문하지 않은것들중 가장 작은 노드'를 찾을 필요도 없다.

 

 

 

---

플로이드 워셜 예제

시간제한 1초 . 데이터 30,000개 

 

📝 체감 난이도 : ★★★☆☆

 

 

🎨 내가 짠 코드 (이진 탐색)

 

 

 

 

 

 

🔑 Key Point 

인접 노드를 알아야 한다. 

 

• 핵심 점화식

 

Graph[a][b] = min(Graph[a][b], Graph[a][k] + Graph[k][b])

 

 

구현하기는 다익스트라보다 쉽다

 

 

 

---

미래 도시

시간제한 1초 . 데이터 100개 

 

 

체감 난이도 : ★★★☆☆

 

 

🎨 내가 짠 코드

 

 

 

 

 

🔑 Key Point 

 

플로이드 워셜 알고리즘의 대표문제 !

우선 주어진 최대 데이터가 굉장히 작다 플로이드는 O(n^3)이므로, 더욱 플로이드를 이용해야겠다고 생각이들 것.

 

---

전보

시간제한 1초 . v=30000 e =. 200000 

 

 

 

체감 난이도 : ★★★☆☆

 

 

🎨 내가 짠 코드

 

 

 

 

🔑 Key Point 

 

 

개선된 다익스트라를 이용할지 , 쉽게 구현할지는 데이터를 보아야하는데 . 노드의 개수는 3만개 이고 간선은 최대 20만개 이다.

따라서, 개선된 다익스트라로 풀어야됨 O(elogv)

 

 

---

마무리

 

뭘 쓸지 아는건 쉽지만 그 이후 구현은 반복밖에 답이 없음.