[2022 KAKAO TECH INTERNSHOP] 등산코스 정하기(118669)

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

 

코드

import sys
from collections import defaultdict
import heapq

sys.setrecursionlimit(10**6)
graph = defaultdict(list)
N = 0
intensity = []

def dijkstra(s, summit, gate):
    global intensity
    
    q = [(0, s)]
    intensity[s] = 0
    
    while q:
        # w, v: 이전 정점으로부터 v까지의 가중치, 현재 정점
        # heap을 사용하여 가중치가 가장 작은 값을 꺼냄
        w, v = heapq.heappop(q)
    	
        # v가 산봉우리인지 확인
        # 변수 summit의 v번째 비트가 0이라면 산봉우리이므로 더 이상 거리 계산을 할 필요 없으니 continue
        if summit & (1 << v) == 0: continue
        # 현재 저장해놓은 v까지의 intensity보다 w가 크다면 계산할 필요 없으니 continue
        if intensity[v] < w: continue
    
    	# _v, _w: v에 연결된 그 다음 정점, 현재 정점 v부터 그다음 정점_v까지의 가중치
        for _v, _w in graph[v]:
        
            # _v가 출발지인지 확인
            # 변수 gate의 _v번째 비트가 0이라면 출발지이므로 갈 수 없으니 continue
            if gate | (1 << _v) == 0: continue
            
            # 현재 저장되어 있는 v정점까지의 최단 intensity와 v부터 _v까지의 가중치를 비교
            # 더 큰값을 cost에 저장해줌
            cost = max(intensity[v], _w)
            
            # 만약 cost가 현재 저장되어 있는 _v정점까지의 최단 intensity보다 작다면
            if cost < intensity[_v]:
            	# 갱신 후 heap에 넣어줌
                intensity[_v] = cost
                heapq.heappush(q, (cost, _v))

    
def solution(n, paths, gates, summits):
    global graph, N, intensity
    
    N = n
    min_intesity = float('inf')
    answer = [0, float('inf')]
    
    for s, e, w in paths:
        graph[s].append((e, w))
        graph[e].append((s, w))
    
    # 각 출발지로부터 각 정점까지의 최단 intensity를 저장하는 배열
    intensity = [float('inf')] * (N+1)
    
    # 각 자리수의 비트가 0일 경우 summit임을 알려주는 변수
    summit = (1 << (N+2)) -1
    # summits을 돌면서 summit 변수의 s번째 비트를 0으로 만들어줌
    for s in summits: summit ^= 1 << s
    
    # 각 자리수의 비트가 0일 경우가 gate임을 알려주는 변수
    gate = (1 << (N+2)) -1
    # gates를 돌면서 gate 변수의 g번째 비트를 0으로 만들어줌
    for g in gates: gate ^= 1 << g
    
    # gates를 하나씩 돌면서 dijkstra 실행
    for g in gates:
        dijkstra(g, summit, gate)
    
    for s in summits:
        if intensity[s] < answer[1]: 
            answer = [s, intensity[s]]
        elif intensity[s] == answer[1]: 
            answer[0] = min(answer[0], s)
    
    return answer

 

풀이

빡센 문제였다 .. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ😇

원래는 gate와 summit을 돌면서 각 gate와 summit에 하나씩 접근하여 최단 intensity를 구하는 완전 탐색 방식으로 풀려고 했는데, 그렇게 푸니까 20~ 24번 테케에서 자꾸 TLE 때려서 최후의 수단(비트연산^^)을 써도 안풀려서 링크의 코드를 참고하여 조금 더 그리디 한 방식으로 코드를 수정했다. (근데 그렇게 해도 안풀려서 비트 연산까지 했다 ..)

 

원래의 다익스트라 알고리즘을 사용했다면 정점 v에 연결되어 있는 그 다음 정점 _v가 visited했는지만 확인하고 heap에 넣어주지만, 시간적 효율성을 위해 현재 v를 거쳐 _v까지 가는 경우의 가중치가 더 작은 경우만 heap에 넣어주는 방식으로 코드를 작성했다.

 

gates의 원소를 시작점으로 하나씩 dijkstra를 돌고 나면 intensity 배열에 모든 시작점으로부터 각 정점까지의 최소 intensity가 저장되므로, summits의 원소를 하나씩 돌면서 각 원소를 인덱스로 한 intensity의 값 중 가장 작은 값을 answer에 담아주면 된다.

 

레벨 3이지만 넘 어렵다... 담에 또 풀어봐야겠다.