Development/CodingTest
์ต๋จ๊ฒฝ๋ก
Kirok Kim
2022. 2. 9. 10:21
ํ๋ก์ด๋ ์์ฌ ์๊ณ ๋ฆฌ์ฆ
- ๋ชจ๋ ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธํ๋ ์ต๋จ๊ฒฝ๋ก
# ์ ์ฒด์ ์ธ ์์๋ก์จ๋ง ์ฐธ๊ณ !
# ๋น์ฉ ๋ฐฐ์ด
values=[2**31-1 for i in range(n)] # ๋ฌธ์ ์์ ๊ฐ์ ธ์จ ๋ฏ
# ๋ฐฉ๋ฌธ ๋ฐฐ์ด
visited =[False for i in range(n)]
# 0๋ฒ ๋
ธ๋๋ฅผ ์์์ ์ผ๋ก ์ค์
start=0
visited[start]=True
values[start]=0
# ๋ฐฉ๋ฌธํ์ง ์์ ๋
ธ๋๊ฐ ์๋ค๋ฉด
while False in visited:
# ๋
ธ๋ ์์ ํ์์ผ๋ก ๋น์ฉ ๋ฐ ๋ฐฐ์ด์ ๊ฑฐ๋ฆฌ ๊ฐ ์ต์ํ
for i in costs:#?? ์ด๊ฑด ์ด๋์ ๋์์ง? ์ด๊ฒ๋ ์์ ๊ฐ ๋
ธ๋๋ณ ๋น์ฉ์ผ๋ก ์์์ด๋จ
if(visited[i[1]]==False and i[0]==start):
values[i[1]]=min(values[i[1]],i[2])
if(visited[i[0]]==False and i[1]==start):
values[i[0]]=min(values[i[0]],i[2])
refer=2**31-1 # ์ด๊ฒ ๋ํ
# ๋ฐฉ๋ฌธํ์ง ์์ ๋
ธ๋ ์ค ์ต์ ๋น์ฉ ๋
ธ๋ ์์น ํ์
for i in range(n):
if(visited[i]==False and values[i]!=0):
refer=min(refer,values[i])
answer = answer + refer
# ํด๋น ๋
ธ๋ ๋ฐฉ๋ฌธ ์ฌ๋ถ ์ฒดํฌ
for i in range(n):
if(visited[i]==False and values[i]==refer):
visited[i]=True
start=i
break
๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ
- ํน์ ๋ ธ๋์์ ๋ค๋ฅธ ๋ ธ๋๊น์ง์ ์ต๋จ ๊ฒฝ๋ก
# ์ ์ฒด์ ์ธ ์์๋ก์จ๋ง ์ฐธ๊ณ !
# ๋น์ฉ ๋ฐฐ์ด
cost=[sys.maxsize for _ in range(n)]
# ๋ฐฉ๋ฌธ ๋ฐฐ์ด
visited =[False for _ in range(n)]
# 0๋ฒ ๋
ธ๋๋ฅผ ์์์ ์ผ๋ก ์ค์
visited[0]=True
cost[0]=0
length=len(visited)
# ๋ฐฉ๋ฌธํ์ง ์์ ๋
ธ๋๊ฐ ์๋ค๋ฉด
while False in visited:
# ๋ฐฉ๋ฌธํ์ง ์์ ์ง์ญ ์ค ์ต์๊ฐ ์ฐพ๊ธฐ
checkLoc=-1
checkValue=sys.maxsize
for i in range(length):
if visited[i]==False and cost[i]<checkValue:
checkLoc=i
checkValue=cost[i]
# ๊ฒ์ฌํ ํ๋ณด๊ฐ ์๋ค๋ฉด ํ์ถ
if checkLoc ==-1:
break
visited[checkLoc]=True
# ๊ฒฝ๋ก ์์ ํ์์ผ๋ก ๋น์ฉ๋ฐฐ์ด ์์
for v1,v2,c in costs:
if v1==checkLoc and visited[v2] ==False:
cost[v2]=min(cost[v2],cost[v1]+c)
if v2==checkLoc and visited[v1] ==False:
cost[v1]=min(cost[v1],cost[v2]+c)
๋ฐ์ํ