Level 2 배달 Python 3

https://programmers.co.kr/learn/courses/30/lessons/12978?language=python3 

코딩테스트 연습 - 배달

 

최종 코드

• Github -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level2_배달.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

from collections import defaultdict, deque
def make_map(road, _map):
    for a, b, c in road:
        _map[a].append([b, c])
        _map[b].append([a, c])
        
def get_order(_map, N, K):
    answer = 1
    visit = [0]*(N+1)
    route = defaultdict(int)
    q = deque()
    visit[1] = 1
    
    for t, dis in _map[1]:
        if dis > K: continue
        if not visit[t]:
            visit[t] = dis
            answer += 1
        elif visit[t] > dis: visit[t] = dis
        q.append([t, dis, [1, t]])
        
    while q:
        now_t, now_dis, now_route = q.popleft()
        if not visit[now_t]:
            answer += 1
            visit[now_t] = now_dis
        for new_t, dis in _map[now_t]:
            if 0 < visit[new_t] < now_dis + dis: continue
            if new_t not in now_route and now_dis+dis <= K:
                now_route.append(new_t)
                q.append([new_t, now_dis + dis, now_route])
                now_route.pop()
            
    return answer  

def solution(N, road, K):
    _map = defaultdict(list)
    make_map(road, _map)
    
    return get_order(_map, N, K)

---

풀이 과정

풀이 시간 53분

테케 3개 정도가 자꾸 시간초과가 나서 해결하는데 시간이 소요되었다.

이유는 이전에 탐색한 루트를 다시 탐색하거나, 1 -> b로 가는 더 빠른 루트가 있는데도 불구하고 다른 루트들을 계속 탐색했기 때문이었다.

이를 보완하기 위해서 visit[b] = 1번 마을에서 b번 마을로 가는 최소 거리를 담아서 현재 탐색하고자 하는 마을이 b인 경우 지금까지 왔던 거리와 비교하여 visit[b] 값이 더 작으면 더이상 탐색하지 않도록 하였다.

from collections import defaultdict, deque
def make_map(road, _map):
    for a, b, c in road:
        _map[a].append([b, c])
        _map[b].append([a, c])
        
def get_order(_map, N, K):
	#적어도 1번 마을에 배달 가능하므로 answer을 1로 초기화
    answer = 1
    
    #1번 마을에서 K이하의 거리로 방문 할 수 있는 마을을 체킹
    #visit[a] = 1번 마을에서 a번 마을로 가는 최소 거리
    visit = [0]*(N+1)
    
    q = deque()
    #1번 마을과 이어져 있는 마을 탐색
    for t, dis in _map[1]:
    	#K 이상의 거리에 있는 경우, 방문 불가
        if dis > K: continue
        
        #t가 이전에 방문하지 않은 마을인 경우, dis 거리를 최솟값으로 설정하고 방문처리 한다
        if not visit[t]:
            visit[t] = dis
            answer += 1
        
        #t 마을에 이전에 방문한 적이 있고 현재 길로 갔을 때 더 가까운 경우, dis 거리로 갱신한다
        elif visit[t] > dis: visit[t] = dis
        
        q.append([t, dis, [1, t]])
        
    while q:
        now_t, now_dis, now_route = q.popleft()
        
        #now_t 마을을 처음 방문한 경우, now_dis 거리로 방문처리 한다
        if not visit[now_t]:
            answer += 1
            visit[now_t] = now_dis
        
        #now_t와 연결된 마을 탐색
        for new_t, dis in _map[now_t]:
        	#이전에 new_t 마을을 방문한 적이 있고 현재 루트로 가는 거리가 더 멀다면, 더이상 가지 않는다
            if 0 < visit[new_t] < now_dis + dis: continue
            
            #지금까지 거쳐온 루트에 new_t가 없으면서(첫 방문) K 이하의 거리인 경우, 이어서 경로를 탐색한다
            if new_t not in now_route and now_dis+dis <= K:
                now_route.append(new_t)
                q.append([new_t, now_dis + dis, now_route])
                now_route.pop()
            
    return answer  

def solution(N, road, K):
	#_map[a] = a 마을과 연결되어 있는 마을과 거리들이 담긴 배열
    _map = defaultdict(list)
    make_map(road, _map)
    
    return get_order(_map, N, K)
    
#시간복잡도 = O(V+E), 공간복잡도 = O(n)