학습 목표

✅ 다익스트라
✅ 플로이드 삼중 for문 

최단 경로

다익스트라

대표적인 최단 경로 탐색

• 결과 : 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로 ( s->e 만 구하는 것이 아님)

• 제약 조건 : 간선(거리)가 음의 값을 가진다면 사용할수 없다.

• 점화 식 :

  if dp[e] > dp[u] + w :
    dp[e] = dp[u] + w
    heapq.heappush(h, (dp[e], e))` 

설명

• 필요한 값
  - 노드간 거리 배열 : 현재 내 코드에서는 2차원 배열
  - 디피 배열 (시작점으로부터의 모든 노드까지의 거리를 저장하는)
  - 방문 여부를 저장하는 방문 배열
  - 미방문 중에서 가장 가까이 위치한 노드 정보를 담는 힙 : ( 선형 탐색으로 구현시 시간 복잡도가 크다)

• 과정

  1. 힙에 탐색할 시작점과 인접한 노드 정보 푸시 + 시작점을 방문 표시
  2. 힙이 빌때까지 아래 과정 반복
     2-1. 힙에서 꺼내기
     2-2. 방문한 노드라면 넘어가기,//해당 노드 방문 처리
     2-3. 다른 노드에 대해서, 해당 노드를 거쳐가서 시작점에 가는 경우가 더 빠른 경우 디피배열 업데이트
     2-4. 업데이트가 일어났다면 힙에 푸시 ()
  3. 디피 배열 완성

다이나믹 프로그래밍 (DP)

• DP는 부분 문제 해를 저장하고 활용한다

큰 문제를 작은 문제로 쪼개서 해결하고, 그 결과를 저장해두고 재활용하는 방식.
“부분 최적해의 누적” = 전체 최적해로 이어진다.
다익스트라는 시작점과 정점사이의 거리를 저장하고 더 짧은 거리를 선택하는 점화식을 사용하며 갱신한다. (여기에 그리디한 선택까지 ! )

플로이드 삼중 for문(플로이드–워셜 알고리즘)

• 결과 : 모든 정점 쌍 최단 거리 구하기

• 제약 조건 : 시간 복잡도가 O(N³)으로 노드 수가 크면 비효율적이다.
  (보통 N ≤ 400 정도까지 실용적)

• 점화 식 :dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

설명

노드 a에서 노드 b로 가는 거리가 노드 c를 거쳐 가는 경우가 더 짧을 수있다.
모든 경우에 대해서 삼중 포문을 돌린다.

초기 상태

from\to	S	2	3	E
S	0	1	∞	10
2	∞	0	1	∞
3	∞	∞	0	1
E	∞	∞	∞	0

k = 2, i = s, j = 3 

dist[s][3] = min(dist[s][3], dit[s][2] + dit[2][3]

k = 2, i = s, j = e
dist[s][e] = min(dist[s][e], dit[s][2] + dit[2][e] => 여긴 갱신 X

➡️ 이때 s -> 3 경로가 2를 거쳐가는 짧은 경로로 업데이트 된다.

from\to	S	2	3	E
S	0	1	2	10
2	∞	0	1	∞
3	∞	∞	0	1
E	∞	∞	∞	0

k = 3, i = s, j = e

dist[s][e] = min(dist[s][3], dit[s][3] + dit[3][e]

➡️ 이때 s -> e 경로 업데이트

from\to	S	2	3	E
S	0	1	2	3
2	∞	0	1	2
3	∞	∞	0	1
E	∞	∞	∞	0

직접 문제 풀어보기

11724 연결요소의 개수

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : 시간, 메모리를 아끼려면 인접 노드 그래프 형식으로 바꿔야한다 ! 노드간에 가중치가 있는 경우에는 [{노드 : 가중치, 노드 : 가중치} ... ] 형식으로 저장
  

1916_최소비용

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : 도착,출발) 이 동일한 버스 노선이 존재할 수 있었다..^^
  

11404_플로이드

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : 플로이드 위셜 알고리즘은 N ≤ 400 정도까지 실용적 이고, k가 가장 바깥 !
  

1956_운동

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : 플로이드?!
  

마무리하면서

꾸준함이 이긴다 !