๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ A์์ B๊น์ง์ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ์ฐพ๊ณ ์ ํ ๋ ์ฌ์ฉํ๋ค.
๋จผ์ , ์๊ณ ๋ฆฌ์ฆ์ ์ง๊ด์ ์ผ๋ก ์ดํด๋ณด์
๋ค์๊ณผ ๊ฐ์ ๊ทธ๋ํ์์ A->C๋ก ๊ฐ๊ณ ์ ํ ๋ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ๊ตฌํด๋ณด์.
์ฐ์ ์ถ๋ฐ์ง๋ก๋ถํฐ ์ธ์ ํ ๋ ธ๋๋ค๊ณผ์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐฑ์ ํ๋ค. (๋นจ๊ฐ์)
๊ทธ ๋ค์ ๋ ธ๋๋ก ์ด๋ํ๋ค.
ํด๋น ๋ ธ๋์์ ์ธ์ ํ ๋ ธ๋๋ค ์ค์ ๋ฐฉ๋ฌธํ์ง ์์ ๋ ธ๋๋ค ๊ณผ์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐฑ์ ํ๋ค.
๋ค์๊ณผ ๊ฐ์ด D์ ๊ฑฐ๋ฆฌ๊ฐ 5์์ 3์ผ๋ก ๊ฐฑ์ ๋์๋ค. (์ต๋จ ๊ฑฐ๋ฆฌ)
C๊ฐ 5์์ 4๋ก ๊ฐฑ์ ๋์๋ค.
ํ์ฌ ๋ฐฉ๋ฌธํ ๋ ธ๋๊ฐ ๋์ฐฉ์ง๋ผ๋ฉด ์๊ณ ๋ฆฌ์ฆ์ ์ข ๋ฃํ๋ค.
๊ทธ๋ฆผ์ฒ๋ผ A->C์ ์ต๋จ๊ฒฝ๋ก๋ 4๊ฐ ๋๋ค. ์์ ๊ฐ์ด ๋์ํ๋ ์๊ณ ๋ฆฌ์ฆ์ด ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
๐ Rule
1. ์ถ๋ฐ ๋ ธ๋๋ก๋ถํฐ ์ธ์ ํ ๋ ธ๋๋ค ์ฌ์ด์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐฑ์ ํ๋ค.
2. ๋ค์ ๋ ธ๋๋ก ๋ฐฉ๋ฌธํ์ฌ ์ธ์ ๋ ธ๋๋ค ์ค ๋ฐฉ๋ฌธํ์ง ์์ ๋ ธ๋๋ค ์ฌ์ด์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐฑ์ ํ๋ค.
3. ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐฑ์ ํ ๋๋ ํ์ฌ ๊ฑฐ๋ฆฌ๊ฐ ์ ์ฅ๋์ด ์๋ ๊ฑฐ๋ฆฌ๋ณด๋ค ์งง์ ๋๋ง ๊ฐฑ์ ํ๋ค.
4. 2,3๋ฒ ๋ฐ๋ณต ํ ๋์ฐฉ์ง์ ๋์ฐฉํ๋ฉด ์๊ณ ๋ฆฌ์ฆ์ ์ข ๋ฃํ๋ค. (๋์ฐฉ ๋ ธ๋์ ์ ์ฅ๋ ๊ฑฐ๋ฆฌ๊ฐ ์ต๋จ๊ฑฐ๋ฆฌ)
Code
dic์ ๋์ ๋๋ฆฌ์ด๋ค. key๋ ๋ ธ๋A value์๋ [๋์ฐฉB, AB์ฌ์ด์ ๊ฑฐ๋ฆฌ]๊ฐ ๋ฆฌ์คํธ๋ก ์ ์ฅ๋์ด์๋ค.
๋ค์ ์ฝ๋๋ ์๋ฐฉํฅ ๊ทธ๋ํ์์ l๋ถํฐ r๊น์ง์ ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ ๋ค์ต์คํธ๋ผ ํจ์์ด๋ค.
import heapq
def dijkstra(n,l,r):
cost=[float('inf') for x in range(n+1)]
h=[(0,l)]
cost[l]=0
while h:
cnt,num=heapq.heappop(h)
if cost[num]<cnt:
continue
for i,j in dic[num]:
if cnt+j<cost[i]:
cost[i]=cnt+j
heapq.heappush(h,(cnt+j,i))
return cost[r]
'๐ Algorithm > Tip' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Python] ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ (DP) (0) | 2022.02.17 |
---|---|
[Python] ์ต์ํ(MIN heap) / ์ต๋ํ(MAX heap) (0) | 2022.01.31 |
[Algorithm] LCA ์๊ณ ๋ฆฌ์ฆ (0) | 2021.03.28 |
[Algorithm] ๋๋น ์ฐ์ ํ์ BFS / ๊น์ด ์ฐ์ ํ์ DFS (0) | 2020.08.24 |