[프로그래머스] 등산코스 정하기 [Level 3] (python 파이썬)

https://school.programmers.co.kr/learn/courses/30/lessons/118669

프로그래머스

 

 

 

 

 

 

 

 

from collections import deque

def solution(n, paths, gates, summits):
    summits = list(set(summits))
    visited = [10000001 for i in range(n+1)]
    graph = [[] for i in range(n+1)]
    start = []
    ans  = []
    
    for gate in gates:
        start.append([gate, 0])
        visited[gate] = 0
    for path in paths:
        graph[path[0]].append([path[1] , path[2]])
        graph[path[1]].append([path[0] , path[2]])
    
    dq = deque(start)
    min = 100000001
    while dq:
        now = dq.popleft()
        if now[1] > min:
            continue
        if now[0] in summits:
            if now[1] <= min:
                min = now[1]
                ans.append(now)
            continue
        next_n = graph[now[0]]
   
        for i in next_n:
            iter = now[1]
            if i[1] > iter:
                iter = i[1]
                
            if visited[i[0]] > iter:
                visited[i[0]] = iter
                dq.append([i[0],iter])
                
    ans.sort(key = lambda x :(x[1], x[0]))

    return ans[0]

1. summits 을 집합으로 만들어 summits의 중복연산을 피한다.

 

 

 

 

 

2. 각각의 지점 번호까지의 최소 intensity를 최댓값인 10000000 보다 큰 값으로 지정한다. (그래야 그래프를 돌면서 최소로 갱신 가능)

 

 

 

 

 

3. 리스트를 하나 생성한 후, paths를 지나면서 각각의 지점번호에 연결된 지점과 시간을 리스트에 해당 인덱스에 집어 넣는다.

(2번 지점에 3,4,5 지점이 연결되고 각각까지의 시간이 1,2,3 이라면 리스트[2] (리스트의 2번째 인덱스) = [[3,1] , [4,2] ,[5,3]] )

 

 

 

 

 

4. 출발지점인 gate를 모두 넣어 덱 생성하기

 

 

 

 

 

5. while 문 안에서 동작 (덱이 empty가 될 때 까지)

 

 

5-1. 현재 지점을 pop하기

 

5-2. 이미 이전에 산봉우리에 도달했을 경우 현재 지점의 intensity가 기존의 intensity(이미 산봉우리에 도달 했을 떄의 intensity) 보다 크면 계산을 할 필요가 없으므로 continue. (intensity의 최소값을 리턴해야 하는데 이미 최솟값보다 크므로 제외)

 

5-3. 만약 현재 지점이 산봉우리인 경우 지금까지의 최소 intensity와 비교하여 같거나 작은 경우, 최솟값 갱신 후, 답에 append. (같은 경우도 넣는 이유는 최소가 여러개일 수 있기 때문.) 

 

5-4 현재 지점과 연결된 지점을 돌면서 다음 지점까지의 시간과 intensity를 비교하면서, intensity를 갱신해나가며 dq에 삽입한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

이 문제를 풀 때는 intensity의 특성을 알아야 한다. 시작점에서부터 올라가면서 intensity는 절대 줄어들지 않으며, 늘기만 한다.

즉, 시작점에서 올라가면서 다음 지점까지의 시간의 최댓값을 저장하고 다음 지점까지 그 정보를 가져와야 한다는 것이다.

 

만약 gate 부터 산봉우리까지의 지점 1,2,3,4가 있고, 각각의 시간이 3-2-4-1 이 걸린다고 해보자

 

 

1. 현재가 3인 경우

맨 처음이므로 intensity = 3

다음 노드 = [2,3] (2지점으로 가고, intensity = 3)

 

 

2. 현재가 2인 경우

intensity 보다 작으므로 intensity에는 변함이 없다. intensity = 3

다음 노드 = [3,3] (3지점으로 가고, intensity = 3)

 

 

3. 현재가 4인 경우

intensity 보다 크므로 intensity가 갱신되다. intensity = 4

다음 노드 = [4,4] (2지점으로 가고, intensity = 4)

 

 

4. 현재가 1인 경우

instensity 보다 작으므로 intensity에는 변함이 없다. intesntiy = 4

현재 노드가 산봉우리이므로 ans에 삽입.

 

 

 

 

 

intensity 는 3 - 3 - 4 - 4 순으로 늘기만 한다.

1~4 번으로 다음 지점으로 갈 때, 위의 경우 처럼 현재 시간과 intensity를 비교하며 dq에 다음 지점을 집어넣어야 한다.

 

 

처음에 덱에 모든 시작 지점을 집어 넣고, 동시에 위의 과정을 수행하면, 각각의 지점에서 시작해서 꼭대기까지의 지점과 intensity가 ans에 하나씩 입력될 것이다. 

 

 

ans에 값이 하나가 입력되는 순간부터, 위의 과정을 수행하는 중 현재 intensity가 ans의 intensity보다 큰 순간 더 이상 현재의 다음 노드를 계산할 필요가 없어진다. (intensity는 항상 증가하기만 하므로 이미 답보다 크므로 더이상 계산할 필요가 없다.)

 

 

이처럼 ans에 값이 하나가 입력되는 순간부터 많은 계산이 제외되므로, 모든 경우의 수를 다 들여다 볼 필요가 없어진다. 

 

 

 

 

 

 

 

위의 과정을 덱이 empty가 될 때 까지 수행하면 ans에는 답의 후보자만이 남을 것이다. 

 

이제 ans의 후보자들을 문제에서 제시한 기준으로 정렬만 하고 답을 출력한다.