[Python/프로그래머스 lv.3] 등산코스 정하기 풀이

Tip

• BFS/DFS
• 백트래킹
• 올라가는 길만 생각하면 됨
• 마지막 시간초과 최적화가 힘들었음..

풀이

1. 무향 가중 그래프를 dict를 통해 나타냈다.

{1: [(4, 4), (6, 1), (7, 3)], 2: [(5, 2)], 3: [(7, 4)], 4: [(1, 4)], 5: [(2, 2), (6, 6)], 6: [(1, 1), (5, 6)], 7: [(1, 3), (3, 4)]}

2. deque를 이용해 BFS 구현
   이때 deque에는 (현재 노드 숫자, 지금까지의 max intensity) 형태로 튜플에 저장

3. dict를 이용해 방문했던 노드들에 대한 최소 w 저장

4. 위에 저장된 정보들로 prune

from collections import deque


def solution(n, paths, gates, summits):
    answer = []
    graph = {}
    dic = {}
    t = deque()
    summits = set(summits)
    gates = set(gates)
    
    for i in range(1,n+1):
        graph[i] = []
        dic[i] = 10000001
        
    for i,j,w in paths:
        graph[i].append((j,w))
        graph[j].append((i,w))
        
    for g in gates:
        t.append((g,-1))
        # heapq.heappush(t, (g,-1))
        
    tt=0
    min_intensity = 10000001
    while len(t)!=0:
        tt,m = t.pop()
        if m>min_intensity or dic[tt]<m:
            continue
        
        if tt in summits and m<=min_intensity:
            if (m!=min_intensity) or (m==min_intensity and answer[0]>tt):
                min_intensity = m
                answer = [tt,m]
                
                print(answer)
            continue
        for j,w in (graph[tt]):
            if (j not in gates and w<=min_intensity):
                temp = (j,w) if w>m else (j,m)
                if temp[1]<dic[temp[0]]:
                    dic[temp[0]] = temp[1]
                    t.append(temp)

    return answer

시간제한으로 인해 마지막에 최적화를 진행하는 게 까다로워서 시간이 오래 걸렸다.
마지막에 생각한 최적화 방법은 다음과 같다.

• 방문한 노드를 딕셔너리로 체크하여 전에 방문했던 경로보다 w가 크면 prune
• 이미 계산 마무리된 경로가 있어서 이를 통해 min_intensity가 업데이트됐다면, 현재 계산하는 노드의 w값이 min_intensity보다 클 경우 prune

if m>min_intensity or dic[tt]<m:
	continue

if temp[1]<dic[temp[0]]:
	dic[temp[0]] = temp[1]
	t.append(temp)

이렇게 해도 두 개의 테스트 케이스가 시간 초과됐는데, 다른 분들 설명을 보다가

for g in gates:

와 같은 코드에서 gates가 리스트일 때 최악의 경우 O(N)이기에 gates를 set으로 변환한 후 진행하라고 하셔서 이걸로 될까 했는데 정말 통과됐다.

소감

처음엔 50%만 정답, 나머지는 모두 시간초과가 떴다. 이런 경우는 보지 못해서 어떻게 하면 시간 복잡도를 줄일 수 있을까 많이 고민했다.
점점 퍼센트를 채워나가 100%를 띄웠을 때 너무 뿌듯했다.
이렇게 꼼꼼히 최적화를 해본 적은 처음이라 좋은 경험이었던 것 같다.
풀이 시간을 줄이려고 노력해야겠다.