プログラマー.出前料理
プログラマー.Level 2. 出前料理
質問リンクhttps://programmers.co.kr/learn/courses/30/lessons/12978
FloyWarshアルゴリズムを使用すると、これらの問題を簡単に解決できます.
質問リンクhttps://programmers.co.kr/learn/courses/30/lessons/12978
FloyWarshアルゴリズムを使用すると、これらの問題を簡単に解決できます.
def solution(N, road, K):
answer = 0
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# 2차원 리스트(그래프 표현)을 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (N+1) for _ in range(N+1)]
# 자기 자신에서 자기 자신으로 가는 거리는 0으로 초기화
for a in range(1, N+1):
for b in range(1, N+1):
if a == b:
graph[a][b] = 0
# 두 마을 a,b를 연결하는 도로는 여러개가 있을 수도 있다고 했으니 min으로 최솟값을 저장
for a, b, c in road:
graph[a][b] = min(graph[a][b], c)
graph[b][a] = min(graph[b][a], c)
# 플로이드 워셜 알고리즘 수행
for k in range(1, N+1):
for a in range(1, N+1):
for b in range(1, N+1):
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
# 걸리는 시간이 K 이하라면 결과값 +1
for a in range(1, N+1):
if graph[1][a] <= K and graph[1][a] != INF:
answer += 1
return answer
Reference
この問題について(プログラマー.出前料理), 我々は、より多くの情報をここで見つけました https://velog.io/@eazyan/프로그래머스.-배달-파이썬-풀이テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol