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)
๋ฐ˜์‘ํ˜•