프로그래머스 배달

문제설명

N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다. 다음은 N = 5, K = 3인 경우의 예시입니다.

위 그림에서 1번 마을에 있는 음식점은 [1, 2, 4, 5] 번 마을까지는 3 이하의 시간에 배달할 수 있습니다. 그러나 3번 마을까지는 3시간 이내로 배달할 수 있는 경로가 없으므로 3번 마을에서는 주문을 받지 않습니다. 따라서 1번 마을에 있는 음식점이 배달 주문을 받을 수 있는 마을은 4개가 됩니다.
마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• 마을의 개수 N은 1 이상 50 이하의 자연수입니다.
• road의 길이(도로 정보의 개수)는 1 이상 2,000 이하입니다.
• road의 각 원소는 마을을 연결하고 있는 각 도로의 정보를 나타냅니다.
• road는 길이가 3인 배열이며, 순서대로 (a, b, c)를 나타냅니다.
  • a, b(1 ≤ a, b ≤ N, a != b)는 도로가 연결하는 두 마을의 번호이며, c(1 ≤ c ≤ 10,000, c는 자연수)는 도로를 지나는데 걸리는 시간입니다.
  • 두 마을 a, b를 연결하는 도로는 여러 개가 있을 수 있습니다.
  • 한 도로의 정보가 여러 번 중복해서 주어지지 않습니다.
• K는 음식 배달이 가능한 시간을 나타내며, 1 이상 500,000 이하입니다.
• 임의의 두 마을간에 항상 이동 가능한 경로가 존재합니다.
• 1번 마을에 있는 음식점이 K 이하의 시간에 배달이 가능한 마을의 개수를 return 하면 됩니다.

입출력예

N	road	K	result
5	[[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]]	3	4
6	[[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]]	4	4

입출력예 설명

입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
주어진 마을과 도로의 모양은 아래 그림과 같습니다.

1번 마을에서 배달에 4시간 이하가 걸리는 마을은 [1, 2, 3, 5] 4개이므로 4를 return 합니다.

풀이

• 처음엔 그냥 브루트 포스(Brute Force)로 대충 따라가보다가 적당히 아무값이나 리턴하려고 했는데... 안됨ㅋ
• 테스트 케이스도 계속 실패.
• 채점 해보니 효율성 테스트는 없고 정확성 테스트만 30개 있다. 정확한 답을 찾는게 중요하다.
• 결국 마을 NxN 2차원 배열에 음식 배달 최대값을 넣었다.

def solution(N, road, K):
    answer = 0
    town = [[500001] * N for i in range(N)]
    
    for _t in town:
        print(_t)
    return answer

테스트 1
출력 〉	
[500001, 500001, 500001, 500001, 500001]
[500001, 500001, 500001, 500001, 500001]
[500001, 500001, 500001, 500001, 500001]
[500001, 500001, 500001, 500001, 500001]
[500001, 500001, 500001, 500001, 500001]

• 이제 road를 순회하고 O(N) 2차원 배열에 값을 채워넣는다.
• 기존에 들어있던 값보다 큰 값일 경우에만 덮어씌운다.
• 그리고 마지막으로 1번 마을에서 1번 마을로 주문하면 당연히 0시간이므로 마지막 답+1 리턴으로 수정한다.

def solution(N, road, K):
    answer = 0
    town = [[500001] * (N+1) for i in range(N+1)]
    
    for (s,e,t) in road:
        town[s][e] = t
        town[e][s] = t
    
    for _t in town:
        print(_t)
    
    return answer + 1
    
테스트 1
출력 〉	
[500001, 500001, 500001, 500001, 500001, 500001]
[500001, 500001, 1, 500001, 2, 500001]
[500001, 1, 500001, 3, 500001, 2]
[500001, 500001, 3, 500001, 500001, 1]
[500001, 2, 500001, 500001, 500001, 2]
[500001, 500001, 2, 1, 2, 500001]

• 여기까지는 대충 만들었는데 이제 어떻게 하느냐?
• 그냥 노가다로 더하면서 K 낮은 값들 계속 저장하는 수 밖에 없나?ㅋㅋㅋ

출발 \ 도착	0	1	2	3	4	5
0	500001	500001	500001	500001	500001	500001
1	500001	500001	1	500001	2	500001
2	500001	1	500001	3	500001	2
3	500001	500001	3	500001	500001	1
4	500001	2	500001	500001	500001	2
5	500001	500001	2	1	2	500001

• 노가다 방식
  • 1번 마을에서 K(=3) 시간안에 도착할 수 있는 마을은...
    • 2번(1시간), 4번(2시간)
      • 2번 마을에서 갈 수 있는 마을은...
        • 1번(1시간), 3번(3시간), 5번(2시간)
          • 1번 : ...
          • 3번 마을에서 갈 수 있는 마을은... 2(3), 5(2)
          • 5번 마을에서 갈 수 있는 마을은... 2(2), 3(1), 4(2)
      • 4번 마을에서 갈 수 있는 마을은...
        • 1번(2시간), 5번(2시간)
          • 1번 ...
          • 5번 ...
• 이거도 배열로 만들면 되겠네?
• 최단 도착 시간 배열.
  • 기존 값보다 작으면 덮어씌우고 계속하면 되고,
  • 기존 값보다 크면 멈추면 됨

마을	0	1	2	3	4	5
초기값	500001	500001	500001	500001	500001	500001
1트	500001	500001	1	500001	2	500001
2트	500001	1+1		1+3

• 그러면 n=n일 경우에는 0을 넣어둬야하겠구나?
• 그래야 이동을 안하네...

def solution(N, road, K):
    answer = 0
    town = [[500001] * (N+1) for i in range(N+1)]
    
    for (s,e,t) in road:
        town[s][e] = t
        town[e][s] = t

    for i in range(N+1):
        town[i][i] = 0
        
    for _t in town:
        print(_t)
    
    return answer + 1
    
테스트 1
출력 〉	
[0, 500001, 500001, 500001, 500001, 500001]
[500001, 0, 1, 500001, 2, 500001]
[500001, 1, 0, 3, 500001, 2]
[500001, 500001, 3, 0, 500001, 1]
[500001, 2, 500001, 500001, 0, 2]
[500001, 500001, 2, 1, 2, 0]

• 최단 도착 시간 배열.
• 0트 : 시작 마을인 1번 마을은 0.
• 1트 : 2번 마을과 4번 마을 도착, 출발 마을의 시간을 합산
  • K 보다 작으면 계속, 기존 값이 더 작으면 계속, 그 외 멈춤 (이건 계속)

마을	0	1	2	3	4	5
초기값	500001	500001	500001	500001	500001	500001
0트 (출발)	500001	0	500001	500001	500001	500001
1트	500001	0	0+1	500001	0+2	500001

• 2트 : 2번 마을과 4번 마을에서 출발
  • 도착할 수 있는 마을은 2 -> 1,3,5 / 4 -> 1 ,5

마을	0	1	2	3	4	5
초기값	500001	500001	500001	500001	500001	500001
0트 (출발)	500001	0	500001	500001	500001	500001
1트	500001	0	0+1 (K보다 작아서 성공)	500001	0+2 (K보다 작아서 성공)	500001
2트	500001	0 0 + 1 (실패) 0 + 2 (실패)	1	500001 0 + 1 + 3 (K보다 커서 실패)	2 0+2	3 0+1+2 (K보다 작아서 성공) 0+2+2 (K보다 커서 실패)

• Q에 더이상 배달할 수 있는 배달원이 없으니까,
  • 최단 도착 시간 배열에서 K보다 작은 값을 찾아서 카운팅해서 리턴
  • 반대로 500001의 갯수를 N에서 빼서 주면? N=5 - 2개 = 3
• 아~ 근데 500001 너무 방해되네?
  • 일단 테스트 케이스트는 9로 풀자!
  • 나중에 되돌리는 거 까먹지 말기

def solution(N, road, K):
    answer = 0
    town = [[500001] * (N+1) for i in range(N+1)]
    shortest_road = town[0] 
    delivery_man = [False] * (N+1)
    
    for (s,e,t) in road:
        if town[s][e] > t:
            town[s][e] = town[e][s] = t
    for i in range(N+1): town[i][i] = 0
    
    shortest_road[1] = 0 # 시작 마을 출발 시간 세팅!
    delivery_man[1] = True # 배달원 출발!
    
    for _t in town: print(_t)
    print("shortest_road:", shortest_road)
    print("delivery_man :", delivery_man)
    
    while sum(delivery_man) > 0: # 배달원이 있는 동안 루프
        for rider in range(1, N+1):
            if delivery_man[rider] == True:
                print(rider,"번 배달원")
                print("shortest_road:", shortest_road)
                for i in range(1, N+1):
                    _time = town[rider][i]
                    _new_time = shortest_road[rider] + _time
                    if _new_time <= K and _new_time < shortest_road[i]:
                        shortest_road[i] = _new_time
                        delivery_man[i] = True
                delivery_man[rider] = False
                print("shortest_road:", shortest_road)
    for i in range(1, N+1):
        if shortest_road[i] < 500001:
            answer += 1
    return answer

• 테스트 케이스는 잘 풀린다. 과연?

테스트 1
입력값 〉	5, [[1, 2, 1], [2, 3, 3], [5, 2, 2], [1, 4, 2], [5, 3, 1], [5, 4, 2]], 3
기댓값 〉	4
실행 결과 〉	테스트를 통과하였습니다.
출력 〉	
[0, 0, 500001, 500001, 500001, 500001]
[500001, 0, 1, 500001, 2, 500001]
[500001, 1, 0, 3, 500001, 2]
[500001, 500001, 3, 0, 500001, 1]
[500001, 2, 500001, 500001, 0, 2]
[500001, 500001, 2, 1, 2, 0]
shortest_road: [0, 0, 500001, 500001, 500001, 500001]
delivery_man : [False, True, False, False, False, False]
1 번 배달원
shortest_road: [0, 0, 500001, 500001, 500001, 500001]
shortest_road: [0, 0, 1, 500001, 2, 500001]
2 번 배달원
shortest_road: [0, 0, 1, 500001, 2, 500001]
shortest_road: [0, 0, 1, 500001, 2, 3]
4 번 배달원
shortest_road: [0, 0, 1, 500001, 2, 3]
shortest_road: [0, 0, 1, 500001, 2, 3]
5 번 배달원
shortest_road: [0, 0, 1, 500001, 2, 3]
shortest_road: [0, 0, 1, 500001, 2, 3]

테스트 2
입력값 〉	6, [[1, 2, 1], [1, 3, 2], [2, 3, 2], [3, 4, 3], [3, 5, 2], [3, 5, 3], [5, 6, 1]], 4
기댓값 〉	4
실행 결과 〉	테스트를 통과하였습니다.
출력 〉	
[0, 0, 500001, 500001, 500001, 500001, 500001]
[500001, 0, 1, 2, 500001, 500001, 500001]
[500001, 1, 0, 2, 500001, 500001, 500001]
[500001, 2, 2, 0, 3, 2, 500001]
[500001, 500001, 500001, 3, 0, 500001, 500001]
[500001, 500001, 500001, 2, 500001, 0, 1]
[500001, 500001, 500001, 500001, 500001, 1, 0]
shortest_road: [0, 0, 500001, 500001, 500001, 500001, 500001]
delivery_man : [False, True, False, False, False, False, False]
1 번 배달원
shortest_road: [0, 0, 500001, 500001, 500001, 500001, 500001]
shortest_road: [0, 0, 1, 2, 500001, 500001, 500001]
2 번 배달원
shortest_road: [0, 0, 1, 2, 500001, 500001, 500001]
shortest_road: [0, 0, 1, 2, 500001, 500001, 500001]
3 번 배달원
shortest_road: [0, 0, 1, 2, 500001, 500001, 500001]
shortest_road: [0, 0, 1, 2, 500001, 4, 500001]
5 번 배달원
shortest_road: [0, 0, 1, 2, 500001, 4, 500001]
shortest_road: [0, 0, 1, 2, 500001, 4, 500001]

• 어? 한번에 성공이야? 왜???
• 이상하다. 이게 성공하네... ㅡ.ㅡ;

정확성  테스트
테스트 1 〉	통과 (0.02ms, 10.3MB)
테스트 2 〉	통과 (0.01ms, 10.3MB)
테스트 3 〉	통과 (0.02ms, 10.3MB)
테스트 4 〉	통과 (0.01ms, 10.3MB)
테스트 5 〉	통과 (0.03ms, 10.3MB)
테스트 6 〉	통과 (0.02ms, 10.4MB)
테스트 7 〉	통과 (0.02ms, 10.3MB)
테스트 8 〉	통과 (0.02ms, 10.3MB)
테스트 9 〉	통과 (0.01ms, 10.3MB)
테스트 10 〉	통과 (0.03ms, 10.2MB)
테스트 11 〉	통과 (0.04ms, 10.4MB)
테스트 12 〉	통과 (0.11ms, 10.3MB)
테스트 13 〉	통과 (0.21ms, 10.4MB)
테스트 14 〉	통과 (0.19ms, 10.3MB)
테스트 15 〉	통과 (0.37ms, 10.5MB)
테스트 16 〉	통과 (0.08ms, 10.4MB)
테스트 17 〉	통과 (0.21ms, 10.3MB)
테스트 18 〉	통과 (0.14ms, 10.2MB)
테스트 19 〉	통과 (0.48ms, 10.3MB)
테스트 20 〉	통과 (0.30ms, 10.4MB)
테스트 21 〉	통과 (0.60ms, 10.5MB)
테스트 22 〉	통과 (0.30ms, 10.3MB)
테스트 23 〉	통과 (0.86ms, 10.4MB)
테스트 24 〉	통과 (0.85ms, 10.4MB)
테스트 25 〉	통과 (0.41ms, 10.4MB)
테스트 26 〉	통과 (0.84ms, 10.5MB)
테스트 27 〉	통과 (0.47ms, 10.6MB)
테스트 28 〉	통과 (0.89ms, 10.6MB)
테스트 29 〉	통과 (0.57ms, 10.5MB)
테스트 30 〉	통과 (0.80ms, 10.5MB)
테스트 31 〉	통과 (0.30ms, 10.3MB)
테스트 32 〉	통과 (0.54ms, 10.3MB)

고수의 풀이

• 코드는 더 짧은데 튀는 구간이 있네?

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)
    
정확성  테스트
테스트 1 〉	통과 (0.02ms, 10.2MB)
테스트 2 〉	통과 (0.02ms, 10.3MB)
테스트 3 〉	통과 (0.02ms, 10.2MB)
테스트 4 〉	통과 (0.04ms, 10.2MB)
테스트 5 〉	통과 (0.03ms, 10.2MB)
테스트 6 〉	통과 (0.02ms, 10.3MB)
테스트 7 〉	통과 (0.02ms, 10.4MB)
테스트 8 〉	통과 (0.02ms, 10.2MB)
테스트 9 〉	통과 (0.02ms, 10.2MB)
테스트 10 〉	통과 (0.02ms, 10.4MB)
테스트 11 〉	통과 (0.02ms, 10.3MB)
테스트 12 〉	통과 (0.11ms, 10.3MB)
테스트 13 〉	통과 (0.07ms, 10.2MB)
테스트 14 〉	통과 (8.59ms, 10.4MB)
테스트 15 〉	통과 (14.15ms, 10.3MB)
테스트 16 〉	통과 (0.04ms, 10.4MB)
테스트 17 〉	통과 (0.06ms, 10.2MB)
테스트 18 〉	통과 (2.43ms, 10.4MB)
테스트 19 〉	통과 (12.19ms, 10.3MB)
테스트 20 〉	통과 (1.71ms, 10.2MB)
테스트 21 〉	통과 (23.51ms, 10.5MB)
테스트 22 〉	통과 (4.09ms, 10.2MB)
테스트 23 〉	통과 (20.51ms, 10.3MB)
테스트 24 〉	통과 (10.55ms, 10.5MB)
테스트 25 〉	통과 (35.28ms, 10.5MB)
테스트 26 〉	통과 (37.42ms, 10.6MB)
테스트 27 〉	통과 (32.64ms, 10.4MB)
테스트 28 〉	통과 (25.05ms, 10.4MB)
테스트 29 〉	통과 (38.29ms, 10.6MB)
테스트 30 〉	통과 (6.95ms, 10.6MB)
테스트 31 〉	통과 (0.15ms, 10.3MB)
테스트 32 〉	통과 (0.54ms, 10MB)

• sys.maxsize 라는게 있구나...

import sys
def solution(N, road, K):
    visited, D, r = [False]*(N+1), [sys.maxsize]*(N+1), [[(None, None)]] + [[] for _ in range(N)]
    for e in road:
        r[e[0]].append((e[1],e[2]))
        r[e[1]].append((e[0],e[2]))
    D[1] = 0
    for _ in range(1,N+1): 
        min_ = sys.maxsize
        for i in range(1,N+1): 
            if not visited[i] and D[i] < min_:
                min_ = D[i]
                m = i
        visited[m] = True
        for w, wt in r[m]:
            if D[m] + wt < D[w]:
                D[w] = D[m] + wt

    return len([d for d in D if d <= K])
    
정확성  테스트
테스트 1 〉	통과 (0.03ms, 10.3MB)
테스트 2 〉	통과 (0.02ms, 10.3MB)
테스트 3 〉	통과 (0.02ms, 10.4MB)
테스트 4 〉	통과 (0.02ms, 10.3MB)
테스트 5 〉	통과 (0.03ms, 10.2MB)
테스트 6 〉	통과 (0.02ms, 10.3MB)
테스트 7 〉	통과 (0.03ms, 10.3MB)
테스트 8 〉	통과 (0.02ms, 10.4MB)
테스트 9 〉	통과 (0.01ms, 10.2MB)
테스트 10 〉	통과 (0.04ms, 10.3MB)
테스트 11 〉	통과 (0.03ms, 10.3MB)
테스트 12 〉	통과 (0.11ms, 10.3MB)
테스트 13 〉	통과 (0.08ms, 10.4MB)
테스트 14 〉	통과 (0.59ms, 10.4MB)
테스트 15 〉	통과 (0.86ms, 10.5MB)
테스트 16 〉	통과 (0.04ms, 10.3MB)
테스트 17 〉	통과 (0.07ms, 10.3MB)
테스트 18 〉	통과 (0.30ms, 10.2MB)
테스트 19 〉	통과 (0.80ms, 10.4MB)
테스트 20 〉	통과 (0.27ms, 10.1MB)
테스트 21 〉	통과 (1.87ms, 10.7MB)
테스트 22 〉	통과 (0.63ms, 10.3MB)
테스트 23 〉	통과 (1.78ms, 10.5MB)
테스트 24 〉	통과 (0.94ms, 10.3MB)
테스트 25 〉	통과 (1.51ms, 10.6MB)
테스트 26 〉	통과 (1.77ms, 10.4MB)
테스트 27 〉	통과 (1.93ms, 10.6MB)
테스트 28 〉	통과 (1.51ms, 10.5MB)
테스트 29 〉	통과 (1.56ms, 10.6MB)
테스트 30 〉	통과 (1.53ms, 10.5MB)
테스트 31 〉	통과 (0.27ms, 10.2MB)
테스트 32 〉	통과 (0.34ms, 10.2MB)

• 다익스트라

import heapq
import sys
inf = sys.maxsize


def dijkstra(start, graph, distance):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i, v in enumerate(graph[now]):
            cost = dist + v
            if cost < distance[i]:
                distance[i] = cost
                heapq.heappush(q, (cost, i))
    return distance


def solution(N, road, K):
    answer = 0
    graph = [[inf for _ in range(N + 1)] for _ in range(N + 1)]
    distance = [inf] * (N + 1)
    for r in road:
        s, e, c = r
        if graph[s][e] < c:
            continue
        graph[s][e] = c
        graph[e][s] = c

    for i in range(N):
        graph[i][i] = 0

    distance = dijkstra(1, graph, distance)
    for item in distance:
        if item <= K:
            answer += 1
    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.03ms, 10.3MB)
테스트 2 〉	통과 (0.02ms, 10.2MB)
테스트 3 〉	통과 (0.08ms, 10.2MB)
테스트 4 〉	통과 (0.05ms, 10.1MB)
테스트 5 〉	통과 (0.05ms, 10.4MB)
테스트 6 〉	통과 (0.05ms, 10.1MB)
테스트 7 〉	통과 (0.02ms, 10.3MB)
테스트 8 〉	통과 (0.02ms, 10.3MB)
테스트 9 〉	통과 (0.01ms, 10.2MB)
테스트 10 〉	통과 (0.03ms, 10.3MB)
테스트 11 〉	통과 (0.03ms, 10.4MB)
테스트 12 〉	통과 (0.21ms, 10.1MB)
테스트 13 〉	통과 (0.16ms, 10.3MB)
테스트 14 〉	통과 (0.30ms, 10.3MB)
테스트 15 〉	통과 (0.41ms, 10.3MB)
테스트 16 〉	통과 (0.12ms, 10.3MB)
테스트 17 〉	통과 (0.25ms, 10.4MB)
테스트 18 〉	통과 (0.71ms, 10.3MB)
테스트 19 〉	통과 (1.05ms, 10.3MB)
테스트 20 〉	통과 (0.76ms, 10.3MB)
테스트 21 〉	통과 (0.96ms, 10.4MB)
테스트 22 〉	통과 (0.42ms, 10.1MB)
테스트 23 〉	통과 (0.65ms, 10.4MB)
테스트 24 〉	통과 (0.49ms, 10.2MB)
테스트 25 〉	통과 (0.70ms, 10.5MB)
테스트 26 〉	통과 (0.62ms, 10.3MB)
테스트 27 〉	통과 (0.60ms, 10.5MB)
테스트 28 〉	통과 (0.66ms, 10.5MB)
테스트 29 〉	통과 (0.66ms, 10.6MB)
테스트 30 〉	통과 (0.60ms, 10.6MB)
테스트 31 〉	통과 (0.33ms, 10.2MB)
테스트 32 〉	통과 (0.35ms, 10MB)

• 왠지 내가 구현한 방식이 제일 빠른 듯?
• 좀 더 최적화 가능하려나?

def solution(N, road, K):
    answer = 0
    town = [[500001] * (N+1) for i in range(N+1)]
    shortest_road = town[0] 
    delivery_man = [False] * (N+1)
    
    for (s,e,t) in road:
        if town[s][e] > t:
            town[s][e] = town[e][s] = t
    for i in range(N+1): town[i][i] = 0
    
    shortest_road[1] = 0 # 시작 마을 출발 시간 세팅!
    delivery_man[1] = True # 배달원 출발!
    
    while sum(delivery_man) > 0: # 배달원이 있는 동안 루프
        for rider in range(1, N+1):
            if delivery_man[rider] == True:
                shortest_road_rider = shortest_road[rider]
                for i in range(1, N+1):
                    if shortest_road[i] != 0:
                        _time = town[rider][i]
                        _new_time = shortest_road_rider + _time
                        if _new_time <= K and _new_time < shortest_road[i]:
                            shortest_road[i] = _new_time
                            delivery_man[i] = True
                delivery_man[rider] = False
    for i in range(1, N+1):
        if shortest_road[i] < 500001:
            answer += 1
    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.02ms, 10.3MB)
테스트 2 〉	통과 (0.01ms, 10.3MB)
테스트 3 〉	통과 (0.02ms, 10.3MB)
테스트 4 〉	통과 (0.01ms, 10.2MB)
테스트 5 〉	통과 (0.02ms, 10.3MB)
테스트 6 〉	통과 (0.02ms, 10.3MB)
테스트 7 〉	통과 (0.03ms, 10.3MB)
테스트 8 〉	통과 (0.01ms, 10.1MB)
테스트 9 〉	통과 (0.01ms, 10.4MB)
테스트 10 〉	통과 (0.03ms, 10.2MB)
테스트 11 〉	통과 (0.03ms, 10.2MB)
테스트 12 〉	통과 (0.12ms, 10.3MB)
테스트 13 〉	통과 (0.12ms, 10.4MB)
테스트 14 〉	통과 (0.19ms, 10.2MB)
테스트 15 〉	통과 (0.36ms, 10.4MB)
테스트 16 〉	통과 (0.06ms, 10.4MB)
테스트 17 〉	통과 (0.11ms, 10.4MB)
테스트 18 〉	통과 (0.15ms, 10.1MB)
테스트 19 〉	통과 (0.24ms, 10.3MB)
테스트 20 〉	통과 (0.43ms, 10.4MB)
테스트 21 〉	통과 (0.33ms, 10.4MB)
테스트 22 〉	통과 (0.33ms, 10.2MB)
테스트 23 〉	통과 (0.53ms, 10.5MB)
테스트 24 〉	통과 (0.47ms, 10.3MB)
테스트 25 〉	통과 (0.43ms, 10.4MB)
테스트 26 〉	통과 (0.48ms, 10.4MB)
테스트 27 〉	통과 (0.48ms, 10.5MB)
테스트 28 〉	통과 (0.51ms, 10.5MB)
테스트 29 〉	통과 (0.62ms, 10.5MB)
테스트 30 〉	통과 (0.58ms, 10.3MB)
테스트 31 〉	통과 (0.31ms, 10.4MB)
테스트 32 〉	통과 (0.30ms, 10.2MB)

• 이거 넣을까 말까 고민했는데...
  • if shortest_road[i] != 0:
  • 뺀 버전이 더 빠르다. 역시 그냥 조건문이든 반복문이든 빼서 코딩 라인 수를 줄이는 게 더 빠른 듯...

넣은 버전

뺀 버전

정확성  테스트 테스트 1 〉 통과 (0.02ms, 10.3MB) 테스트 2 〉 통과 (0.01ms, 10.3MB) 테스트 3 〉 통과 (0.02ms, 10.3MB) 테스트 4 〉 통과 (0.01ms, 10.2MB) 테스트 5 〉 통과 (0.02ms, 10.3MB) 테스트 6 〉 통과 (0.02ms, 10.3MB) 테스트 7 〉 통과 (0.03ms, 10.3MB) 테스트 8 〉 통과 (0.01ms, 10.1MB) 테스트 9 〉 통과 (0.01ms, 10.4MB) 테스트 10 〉 통과 (0.03ms, 10.2MB) 테스트 11 〉 통과 (0.03ms, 10.2MB) 테스트 12 〉 통과 (0.12ms, 10.3MB) 테스트 13 〉 통과 (0.12ms, 10.4MB) 테스트 14 〉 통과 (0.19ms, 10.2MB) 테스트 15 〉 통과 (0.36ms, 10.4MB) 테스트 16 〉 통과 (0.06ms, 10.4MB) 테스트 17 〉 통과 (0.11ms, 10.4MB) 테스트 18 〉 통과 (0.15ms, 10.1MB) 테스트 19 〉 통과 (0.24ms, 10.3MB) 테스트 20 〉 통과 (0.43ms, 10.4MB) 테스트 21 〉 통과 (0.33ms, 10.4MB) 테스트 22 〉 통과 (0.33ms, 10.2MB) 테스트 23 〉 통과 (0.53ms, 10.5MB) 테스트 24 〉 통과 (0.47ms, 10.3MB) 테스트 25 〉 통과 (0.43ms, 10.4MB) 테스트 26 〉 통과 (0.48ms, 10.4MB) 테스트 27 〉 통과 (0.48ms, 10.5MB) 테스트 28 〉 통과 (0.51ms, 10.5MB) 테스트 29 〉 통과 (0.62ms, 10.5MB) 테스트 30 〉 통과 (0.58ms, 10.3MB) 테스트 31 〉 통과 (0.31ms, 10.4MB) 테스트 32 〉 통과 (0.30ms, 10.2MB)

정확성  테스트 테스트 1 〉 통과 (0.02ms, 10.3MB) 테스트 2 〉 통과 (0.01ms, 10.3MB) 테스트 3 〉 통과 (0.02ms, 10.3MB) 테스트 4 〉 통과 (0.01ms, 10.4MB) 테스트 5 〉 통과 (0.03ms, 10.3MB) 테스트 6 〉 통과 (0.02ms, 10.4MB) 테스트 7 〉 통과 (0.02ms, 10.4MB) 테스트 8 〉 통과 (0.01ms, 10.3MB) 테스트 9 〉 통과 (0.01ms, 10.4MB) 테스트 10 〉 통과 (0.03ms, 10.3MB) 테스트 11 〉 통과 (0.04ms, 10.3MB) 테스트 12 〉 통과 (0.18ms, 10.3MB) 테스트 13 〉 통과 (0.18ms, 10.2MB) 테스트 14 〉 통과 (0.18ms, 10.2MB) 테스트 15 〉 통과 (0.63ms, 10.2MB) 테스트 16 〉 통과 (0.05ms, 10.4MB) 테스트 17 〉 통과 (0.09ms, 10.4MB) 테스트 18 〉 통과 (0.13ms, 10.4MB) 테스트 19 〉 통과 (0.23ms, 10.3MB) 테스트 20 〉 통과 (0.19ms, 10.4MB) 테스트 21 〉 통과 (0.34ms, 10.3MB) 테스트 22 〉 통과 (0.27ms, 10.2MB) 테스트 23 〉 통과 (0.58ms, 10.4MB) 테스트 24 〉 통과 (0.40ms, 10.3MB) 테스트 25 〉 통과 (0.39ms, 10.4MB) 테스트 26 〉 통과 (0.43ms, 10.6MB) 테스트 27 〉 통과 (0.42ms, 10.3MB) 테스트 28 〉 통과 (0.45ms, 10.6MB) 테스트 29 〉 통과 (0.53ms, 10.4MB) 테스트 30 〉 통과 (0.44ms, 10.5MB) 테스트 31 〉 통과 (0.24ms, 10.3MB) 테스트 32 〉 통과 (0.25ms, 10.2MB)

오늘은 한방에 성공해서 기분이 날아갈 것 같다.