[소프티어] 지우는 소수를 좋아해 (파이썬)

난이도 : ★★★★☆

 

https://softeer.ai/practice/info.do?idx=1&eid=582 

Softeer

 

📄 문제

• 여러 체육관을 거쳐 체육관 배지를 얻은 후 마지막 포켓몬 리그에서 사천왕과 챔피언에게 도전해야 하는 임무
• 각각의 체육관에는 체육관 관장들이 있고 그 관장들을 이겨야 체육관 배지를 얻을 수 있다.
• 관장들을 이기기 위해선 그 관장들이 갖고 있는 레벨(level)보다 높아야 한다.
• 체육관 관장들은 체육관 오는 길에 레벨 제한을 두었다. ‘X레벨 이하 지원자는 오지 마시오.’

• 지우는 자신이 포켓몬 리그에 나가기 위한 최소한의 레벨이 알고 싶어졌다.
• 지우는 자신의 레벨도 소수(Prime Number)에 맞춰서 포켓몬 리그에 참여하고 싶어 한다.
• 지우는 항상 1번 체육관에서부터 출발하고 마지막 N번 체육관을 지나가야 마지막 포켓몬 리그로 갈 수 있다. ★

 

지우의 조건을 맞추어 지우에게 각각의 체육관을 넘어 마지막 장소인 포켓몬 리그에 참여할 수 있는 최소한의 레벨을 알려주는 프로그램을 작성해보자.

 

---

💡 아이디어

1. A번 체육관과 B번 체육관 사이에 필요 레벨이 C인 길이 존재한다.
   • a,b 사이에 값이 존재한다. (다익스트라 사용)
2. 최소 레벨 경로를 찾는 함수가 필요하다.
   1. 각 체육관을 돌면서 필요 레벨의 최대 값이 최소가 되는 경로를 찾는다.
   2. 최소 레벨 경로 안에서 최대 레벨을 찾는다.
3. 소수를 찾는 함수가 필요하다.
   • 찾은 최대 레벨보다 큰, 가장 가까운 소수를 찾는다.

 

반응형

 

📝 문제 풀이 (Code)

import sys, heapq

# 소수 찾기
def is_prime_number(num):
    for k in range(2, num):
        if num % k == 0:
            return False
    return True


# 최소 경로 찾기
def dijkstra():
    maxV = 1000000001
    visited = [maxV] * (n + 1)
    visited[0] = 0

    # 레벨, 위치
    heap = [(0, 1)]
    visited[1] = 0

    while heap:

        level, curr = heapq.heappop(heap)

        if curr == n:
            continue

        if visited[curr] < level:
            continue

        for posi, new_level in gym[curr]:
            # 경로 중 최대 level을 업데이트
            max_level = max(new_level, level)
            if max_level < visited[posi]:
                visited[posi] = max_level
                heapq.heappush(heap, (max_level, posi))

    return visited[n]


# ★ 항상 1번 체육관에서부터 출발하고 마지막 N번 체육관을 지나가야 마지막 포켓몬 리그로 갈 수 있다.
# 1. 소수 찾는 함수
# 2. 레벨 체크 하는 함수

# 체육관의 개수를 나타내는 정수 N과 체육관 사이의 길의 개수 정수 M
n, m = map(int, input().split())
gym = [[] for _ in range(n + 1)]

# A번 체육관과 B번 체육관 사이에 필요 레벨이 C인 길이 존재한다. (a,b 사이에 값이 존재 - 다익스트라)
for _ in range(m):
    a, b, c = map(int, input().split())
    gym[a].append((b, c))
    gym[b].append((a, c))

# 관장 최소 레벨 찾기
num = dijkstra()
# 관장들이 갖고 있는 레벨(level)보다 높아야 함
num += 1

# 소수 찾기
while not is_prime_number(num):
    num += 1

print(num)