260825 업그레이드
- 0) 시작정점에서부터 모든 정점에 대한 최단거리를 구함.
- 0-1) bfs와는 다르게 가중치가 모두 다르다.
- 0-2) distTable 필요.
- 1) bfs처럼 시작정점에서부터 시작함.
- 2) 그리디 : 매순간 최고의 선택을 하는데, 매순간 가중치가 짧은 가중치를 먼저 처리하려고 하므로, 그리디이다.
- 3) bfs와는 달리 타겟정점과 해당정점까지의 최단거리를 쌍으로 넣음.
-> 그래야 다른 경로로 접근하는 "가중치,정점번호" 와 비교가 가능하므로, - 4) INF값은 987654321 로 하자.
int_max 로 하게되면, int_max + intr_max 더하는 순간 데이터초과이다.
음의 가중치가 없기 때문에 지금 상황에서 1번 입장에서 최고의 선택은 1->3번으로 가는 방법이다.
코드 주의할점
-
0) bfs와는 다르게 visited 없이도, dist테이블 값만으로
조건 처리가 가능함. -
1) 시간초과 방지하기 위해서 반드시 작성하자.
이미 현재 dist가 비교하려는 경로상의 dist보다 좋다면 굳이 진행할 필요 없다.
- 2) 초기화는 fill 사용하자.
: memset은 -1,0 초기화할때만 사용하고,
-> 32비트는 초기화가 불가하므로 fill 사용하자.
- 3) INT_MAX 사용 금지.
-> 처음에 진행시 dist + 다른 dist로 INT_MAX + INT_MAX 하는 경우에
OVER-FLOW 발생하므로,987654321 을 사용하자. // 종만북 특정값.
프로그래머스 : 배달문제
- 어쨋든 문제에서 제시된 그래프의 연결상태를 주의하자.
-> 지금의 경우 지문에서 양방향이라고 하므로,
그래프의 모든 정점을 양방향으로 해야함.
다익스트라 응용 문제
🔥🔥🔥