[์ด์ทจ์ฝ-์ต๋จ ๊ฒฝ๋ก] ๊ฐ์ ๋ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ / Python
๐ Problem Solving/์ด์ทจ์ฝ
์ ๋ ฅ
1. ๋ ธ๋ ๊ฐ์, ๊ฐ์ ๊ฐ์ ์ ๋ ฅ
2. ์์ ๋ ธ๋ ์ ๋ ฅ
3. ๊ฐ์ ๊ฐ์์ ๋ผ์ธ๋งํผ a, b, c ์ ๋ ฅ (a -> b, c์ ๋น์ฉ)
์ถ๋ ฅ
์์๋ ธ๋๋ก๋ถํฐ ๊ฐ ๋ ธ๋๊น์ง์ ๋น์ฉ ์ถ๋ ฅ
import heapq
INF = int(1e9) # ๋ฌดํ์ ์๋ฏธํ๋ ๊ฐ์ผ๋ก 10์ต์ ์ค์
# ๋
ธ๋์ ๊ฐ์, ๊ฐ์ ์ ๊ฐ์๋ฅผ ์
๋ ฅ๋ฐ๊ธฐ
n, m = map(int, input().split())
# ์์ ๋
ธ๋ ๋ฒํธ๋ฅผ ์
๋ ฅ๋ฐ๊ธฐ
start = int(input())
# ๊ฐ ๋
ธ๋์ ์ฐ๊ฒฐ๋์ด ์๋ ๋
ธ๋์ ๋ํ ์ ๋ณด๋ฅผ ๋ด๋ ๋ฆฌ์คํธ๋ฅผ ๋ง๋ค๊ธฐ
graph = [[] for i in range(n + 1)]
# ์ต๋จ ๊ฑฐ๋ฆฌ ํ
์ด๋ธ์ ๋ชจ๋ ๋ฌดํ์ผ๋ก ์ด๊ธฐํ
distance = [INF] * (n + 1)
# ๋ชจ๋ ๊ฐ์ ์ ๋ณด๋ฅผ ์
๋ ฅ๋ฐ๊ธฐ
for _ in range(m):
a, b, c = map(int, input().split())
# a๋ฒ ๋
ธ๋์์ b๋ฒ ๋
ธ๋๋ก ๊ฐ๋ ๋น์ฉ์ด c๋ผ๋ ์๋ฏธ
graph[a].append((b, c))
def dijkstra(start):
q = []
# ์์ ๋
ธ๋๋ก ๊ฐ๊ธฐ ์ํ ์ต๋จ ๊ฒฝ๋ก๋ 0์ผ๋ก ์ค์ ํ์ฌ, ํ์ ์ฝ์
heapq.heappush(q, (0, start))
distance[start] = 0
while q: # ํ๊ฐ ๋น์ด์์ง ์๋ค๋ฉด
# ๊ฐ์ฅ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ์งง์ ๋
ธ๋์ ๋ํ ์ ๋ณด ๊บผ๋ด๊ธฐ
dist, now = heapq.heappop(q)
# ํ์ฌ ๋
ธ๋๊ฐ ์ด๋ฏธ ์ฒ๋ฆฌ๋ ์ ์ด ์๋ ๋
ธ๋๋ผ๋ฉด ๋ฌด์
if distance[now] < dist:
continue
# ํ์ฌ ๋
ธ๋์ ์ฐ๊ฒฐ๋ ๋ค๋ฅธ ์ธ์ ํ ๋
ธ๋๋ค์ ํ์ธ
for i in graph[now]:
cost = dist + i[1]
# ํ์ฌ ๋
ธ๋๋ฅผ ๊ฑฐ์ณ์, ๋ค๋ฅธ ๋
ธ๋๋ก ์ด๋ํ๋ ๊ฑฐ๋ฆฌ๊ฐ ๋ ์งง์ ๊ฒฝ์ฐ
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
# ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ์ํ
dijkstra(start)
# ๋ชจ๋ ๋
ธ๋๋ก ๊ฐ๊ธฐ ์ํ ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ์ถ๋ ฅ
for i in range(1, n + 1):
# ๋๋ฌํ ์ ์๋ ๊ฒฝ์ฐ, ๋ฌดํ(INFINITY)์ด๋ผ๊ณ ์ถ๋ ฅ
if distance[i] == INF:
print("INFINITY")
# ๋๋ฌํ ์ ์๋ ๊ฒฝ์ฐ ๊ฑฐ๋ฆฌ๋ฅผ ์ถ๋ ฅ
else:
print(distance[i])
ํด์ค
์ต๋จ ๊ฒฝ๋ก ๋ฌธ์ ๋ค์ ํ๊ธฐ ์ ์ ์์์ ๊ธฐ๋ณธ์ ์ธ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ ์์ค์ฝ๋๋ฅผ ๋ณต์ตํ๋ค.
๋ณต์ตํ๋ ์ด์ ์ ๊ณต๋ถํ๋ ๋ถ๋ถ๋ค์ด ๋ค์ ์๊ฐ์ด ๋๊ธฐ ์์ํ๋ค๐
'๐ Problem Solving > ์ด์ทจ์ฝ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์ด์ทจ์ฝ-๊ทธ๋ํ ์ด๋ก ] ๊ฐ์ ๋ ์๋ก์ ์งํฉ ์๊ณ ๋ฆฌ์ฆ ์์ค์ฝ๋ / Python (0) | 2021.07.01 |
---|---|
[์ด์ทจ์ฝ-์ต๋จ๊ฒฝ๋ก] ์ ๋ณด / Python (0) | 2021.07.01 |