[프로그래머스]배달
프로그래머스
배달
링크 : 문제 바로가기
def solution(N, road, K):
answer = 0
cost = [ 9876543210 ]*(N+1)
cost[1] = 0
visited = [ False ]*(N+1)
road_chain = [ [] for _ in range(N+1) ]
for data in road:
road_chain[data[0]].append((data[1],data[2]))
road_chain[data[1]].append((data[0],data[2]))
node = 1
for i in range(N):
visited[node]=True
best_node = 0
best_cost = 9876543210
# 한 노드에서 뻗친 노드들 검토
check=0 # 이동할 다음 노드가 존재하는지 확인용
for node_and_cost in road_chain[node]:
new_node=node_and_cost[0]
new_cost=node_and_cost[1]
# 일단 해당 노드에 연결된 노드들 비용 모두 갱신
if cost[new_node]>cost[node]+new_cost:
cost[new_node]=cost[node]+new_cost
for check in range(1,N+1):
if visited[check]==False and cost[check]<best_cost:
best_cost=cost[check]
best_node=check
node=best_node
for cnt_cost in cost[1:]:
if cnt_cost<=K:
answer+=1
print(cost)
return answer
이 문제의 경우 계속해서 오답처리가 되어 고민을 많이 했던 문제다. 그 이유는 다익스트라 알고리즘에 대한 잘못된 이해였다. 나는 다익스트라 알고리즘에서 시작노드에서 다음노드로 넘어가는 경우에서 조건이 방문하지 않은 노드이며, 가장 최단 비용을 가지고 있는 노드로 이동한다는 것을 알고 있었다. 하지만 범위가 전체인 것을 몰랐다. 예를 들어 1번 노드에서 2번 노드로 이동하였으면, 2번 노드와 연결된 노드 중 방문하지 않은 노드이며, 가장 최단 비용을 가지고 있는 노드로 생각을 했다. 하지만 이 때는 전체노드 중 방문하지 않은 노드이며, 가장 최단 비용을 가지고 있는 노드로 다음 노드를 설정해야 했다. 이를 고쳐서 위와 같은 코드로 문제를 풀 수 있었다.
알고리즘 : 다익스트라 알고리즘