[프로그래머스/python] 배달
2022. 8. 23. 16:15ㆍ알고리즘/프로그래머스
반응형
배달
Summer/Winter Coding(~2018)
문제
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
풀이
다익스트라로 풀었습니다.
풀이코드
def min_index(li,visit):
min_val = 9999999
min_idx = 0
for i in range(len(li)):
if li[i]==0 or visit[i]==True:
continue
if li[i]<=min_val:
min_idx = i
min_val = li[i]
return min_idx
def solution(N, road, K):
answer = 0
node_map = [[500001 for j in range(N+1)] for i in range(N+1)]
road.sort()
v = [False for i in range(N+1)]
for i in road:
start, end, dist = i
node_map[start][end] = min(dist,node_map[start][end])
node_map[end][start] = min(dist,node_map[end][start])
dist = node_map[1]
dist[1] = 0
v[1] = True
v[0] = True
for i in range(N-1):
current = min_index(dist,v)
v[current] = True
for j in range(1, N+1):
if not v[j]:
if dist[current] + node_map[current][j] <= dist[j] :
dist[j] = dist[current] + node_map[current][j]
answer = 0
for i in dist:
if K>=i:
answer+=1
return answer
가장 인기 많은 코드
def solution(N, road, K):
visited = [False] * (N + 1)
costs = [float('inf')] * (N + 1)
costs[1] = 0
parents = [1]
while (parents):
parent = parents.pop(0)
visited[parent] = True
for a, b, cost in road:
if (a == parent or b == parent):
target = b if a == parent else a
if costs[target] > costs[parent] + cost:
costs[target] = costs[parent] + cost
parents.append(target)
return sum(1 for c in costs if c <= K)
반응형
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스/python] 영어 끝말잇기 (0) | 2022.08.23 |
---|---|
[프로그래머스/python] 삼각달팽이 (0) | 2022.08.23 |
[프로그래머스/python] 두 큐 합 같게만들기 (0) | 2022.08.23 |
[프로그래머스/python] 추석트래픽 (0) | 2022.08.23 |
[프로그래머스/javascript] 3진법 뒤집기 (0) | 2022.08.15 |