[Softeer](LV 4) 지우는 소수를 좋아해

문제 링크

LV 4: 지우는 소수를 좋아해

구현 방식

• dijkstra 응용 문제이다
  • costs 또는 distances table 대신에 levels table을 정의해주었다
    • dijkstra(1)을 수행해주면, levels table에는 1번 체육관에서부터 각 체육관까지 도달 가능한 최소 레벨이 저장됨
  • tlevel = max(clevel, nlevel)으로 할당해주고, tlevel < levels[next]를 만족한다면 levels[next]를 갱신해주고 해당 노드를 heap에 추가한다
• 최소 비용 경로 -> dijkstra (dijkstra는 최소 비용 경로라면, 중복 노드 방문도 가능함)

코드

import sys
import heapq
import math

N, M = map(int, sys.stdin.readline().split())
edges = dict()
for m in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    if A in edges: edges[A].append((B, C))
    else: edges[A] = [(B, C)]
    if B in edges: edges[B].append((A, C))
    else: edges[B] = [(A, C)]

def isPrime(x):
    for i in range(2, int(math.sqrt(x))+1):
        if x%i==0: return False
    return True

def dijkstra(start):
    levels[start] = 0
    heap = []
    heapq.heappush(heap, [levels[start], start])

    while heap:
        clevel, curr = heapq.heappop(heap)
        if clevel > levels[curr]: continue

        if curr in edges:
            for next, nlevel in edges[curr]:
                tlevel = max(clevel, nlevel)
                if tlevel < levels[next]:
                    levels[next] = tlevel
                    heapq.heappush(heap, [tlevel, next])


# 최소 비용 -> dijkstra (dijkstra는 최소 비용 경로라면, 중복 노드 방문도 가능함)
levels = [int(1e9) for i in range(N+1)] # 1번 체육관에서부터 각 체육관 까지 도달 가능한 최소 레벨
dijkstra(1)

answer = levels[N]+1 # "X레벨 이하 지원자는 오지 마시오."
if isPrime(answer): print(answer)
else:
    answer += 1
    while True:
        if isPrime(answer): print(answer); break
        answer += 1