[파이썬] Softeer 연습문제 #19. 지우는 소수를 좋아해 완벽해설

문제

 

https://softeer.ai/practice/6272

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

 

해설

 

너비우선탐색과 동적 프로그래밍의 응용 알고리즘인 "다익스트라(dijkstra) 알고리즘" + "소수를 판단하는 로직" 을 통해 구현해낼 수 있게 된다.

 

다익스트라 알고리즘이라는 것은 하나의 "최단 거리 탐색"을 위해 주로 사용되는 알고리즘이다. 

 

https://m.blog.naver.com/ndb796/221234424646

23. 다익스트라(Dijkstra) 알고리즘

 

이 개념에 대한 설명은 위 링크에 잘 나와 있으니 참고하길 바라며, 간단하게 설명하자면, "최단 거리 탐색" 알고리즘은 어떤 장소들이 존재하고, 그 장소들 사이에 길들과 거리가 주어져 있을 때, 하나의 장소에서 목적지가 되는 장소까지 도달하는데 필요한 최소 거리를 알아내는 알고리즘이다.

 

다만 소프티어에서 주어진 이 문제는 최소 거리를 구하는 게 아니라, 첫번째 체육관에서 마지막 체육관에 도달하기 위해서 필요한 "최소 레벨 수"를 구하는 것이 목적이다.

 

그 과정에서 첫번째 체육관에서 마지막 체육관까지 도달하기 위한 경로에서 필요한 길들을 거치는데, 거쳐온 길들에서 요구되는 "최대 레벨"이 결국 마지막 체육관에 도달하기 위해서 필요한 레벨이 되며, 결국에는 모든 경로들의 경우의 수 중에서 "요구되는 '최대 레벨' "의 "최소 레벨"을 구하게 되면 결국 지우가 마지막 포켓몬 리그에 갈 수 있는 최소한의 레벨을 구할 수 있게 된다.

 

이 과정에서도 다익스트라 알고리즘이 충분히 활용될 수가 있다. 여기서는 개념 설명 링크에서 설명한 두번째 코드인 "인접 리스트 방식"을 활용하여 구현이 되었다.

 

 

import sys
from collections import deque
import math

N, M = map(int, sys.stdin.readline().split())
moves = [[] for _ in range(N+1)]
dp = [math.inf for _ in range(N+1)]

# 각각의 움직임과 그에 필요한 최소 레벨을 담아준다.
for _ in range(M):
  A, B, C = map(int, sys.stdin.readline().split())
  moves[A].append([B, C])
  moves[B].append([A, C])

 

코드를 작성하기에 앞서 위의 코드를 통해 필요한 변수들을 준비하고, 입력된 변수를 받아 저장하는 코드를 작성해준다.

여기서 moves 변수는 이 문제에서 입력되는 [목적지, 요구되는 레벨] 에 대한 모든 데이터를 담기 위해서 사용이 되며, dp의 경우는 각각의 체육관에서 요구되는 최소 레벨을 담아주기 위한 변수이다.

 

 

# 다익스트라 알고리즘
def dijkstra(start_point):
  # 큐를 사용해 힙 자료구조를 준비해준다.
  queue = deque()
  # 시작점과 누적 레벨을 넣어준다.
  queue.append([start_point, 0])

  while queue:
    # 초기 위치랑 누적 레벨을 가져온다.
    dest, level = queue.popleft()
    
    # 만약 동적프로그래밍 리스트에 담긴 최소 레벨보다 높은 경우는 바로 해당 루프를 끝낸다.
    # (아예 가능성 없는 애들은 계산을 안하기 위함.)
    if (level > dp[dest]):
      continue

    # 다음 이동을 시뮬레이션 한다.
    for new_dest, new_level in moves[dest]:
      # 이전 길에서의 필요 레벨과 다음 길에서의 필요 레벨의 최대값을 저장해주고,
      max_level = max(level, new_level)
      # 만약 그 레벨이 그 위치에서의 누적 최소 레벨보다 작을 경우
      if max_level < dp[new_dest]:
        # 그 누적 최소 레벨에 해당 최대 레벨을 담아준다.
        dp[new_dest] = max_level
        # 그리고 새로운 목적지에 새로운 필요 최소 레벨을 갱신해준 후 담아준다.
        queue.append([new_dest, max_level])

  # 마지막 위치에 누적 계산을 통해 저장된 필요 최소 레벨을 출력해준다.
  return dp[-1]

 

 

그리고 나서 코드를 작성하게 되면 위와 같다. 

이 방법의 핵심을 요약하자면

1. 완전 탐색을 위해 힙 자료구조 (큐 : queue) 를 사용하고,
2. 처음 위치부터 시작하여 각 위치에서 moves에 저장된 이동 정보를 통해 움직임을 진행하는데,
3. 이전 길에서 필요한 레벨(level)과 다음 길에서 필요한 레벨(new_level)의 최대 레벨값을 구하고,
4. 만약 그 최대값이 도착하는 체육관에서의 누적 최소 레벨값 (dp[new_dest])보다 작을 경우 dp[new_dest]를 그 최대 레벨값으로 갱신해주고,
5. 새로운 위치와 최대 레벨값 [new_dest, max_level] 을 큐에 다시 담아준 후 다시 다음 루프를 돌린다.

위와 같이 표현할 수 있다.

 

지우는 지나온 모든 길에서 요구되는 레벨 중 가장 최대값 보다 높은 레벨을 가져야만 한다. 그렇기에 4번 과정을 통해 지나온 길들의 최대 레벨을 구함으로써 각각의 경로를 지날 수 있기 위해 요구되는 최소 레벨 수를 구할 수 있게 되며, 그 모든 경로에서 요구되는 최소 레벨 수를 dp에 담고 나서 모든 계산이 끝났을 때 dp의 마지막 위치에서의 값을 출력해주면 최소 요구 레벨을 구할 수 있게 된다.

 

min_level = dijkstra(1)

# 소수인지를 확인해주는 코드 (조건 : num >= 2 여야 함.)
# 소수의 의미: 숫자 num이 있을 때, 1과 num을 제외하고 나눗셈의 나머지가 0인 수가 없어야 함.
def b_prime(num):
  for i in range(2, int(math.sqrt(num))+1):
    if (num % i == 0):
      return False
  return True
  
# 포켓몬의 최소 레벨은 체육관 최소 요구 레벨보다 높아야 한다.
for i in range(min_level+1, 2*min_level):
  # 최소 요구 레벨이 0~1이라면 2를 출력.
  if (min_level <= 1):
    print(2)
    break
  else:
    if (b_prime(i)):
      print(i)
      break

 

그리고 나서 지우는 "소수"를 좋아하기 때문에 마지막으로 위 코드를 통해 "요구되는 최소 레벨"을 토대로 이보다 높으면서도 가장 가까운 소수 값을 구해줄 수 있게 된다. 

 

소수에 대한 조건은 자기 자신과 1 빼고는 나눗셈에 대한 나머지가 0인 값이 존재하지 않아야만 한다. 이를 실현시키기 위해서 "정수 2"부터 시작해서 "자기자신 - 1" 까지 계속 나눠가며 모든 값에 대해서 나머지가 0이 되는 경우가 존재하지 않으면 소수가 된다.

 

하지만 계산량을 줄이기 위해 "자기자신 - 1" 대신 "자기자신의 제곱근 + 1" 까지만 돌려도 문제가 없다. 마지막으로 최소 레벨이 0이거나 1인 경우에 대비해서는 그에 가장 가까운 소수 "2"를 출력하도록 설정해주면 이 문제의 코드 작성이 모두 완료되었다.

 

 

코드

import sys
from collections import deque
import math

N, M = map(int, sys.stdin.readline().split())
moves = [[] for _ in range(N+1)]
dp = [math.inf for _ in range(N+1)]

# 각각의 움직임과 그에 필요한 최소 레벨을 담아준다.
for _ in range(M):
  A, B, C = map(int, sys.stdin.readline().split())
  moves[A].append([B, C])
  moves[B].append([A, C])

def dijkstra(start_point):
  # 큐를 사용해 힙 자료구조를 준비해준다.
  queue = deque()
  # 시작점과 누적 레벨을 넣어준다.
  queue.append([start_point, 0])

  while queue:
    # 초기 위치랑 누적 레벨을 가져온다.
    dest, level = queue.popleft()
    
    # 만약 동적프로그래밍 리스트에 담긴 최소 레벨보다 높은 경우는 바로 해당 루프를 끝낸다.
    # (아예 가능성 없는 애들은 계산을 안하기 위함.)
    if (level > dp[dest]):
      continue

    # 다음 이동을 시뮬레이션 한다.
    for new_dest, new_level in moves[dest]:
      # 이전 길에서의 필요 레벨과 다음 길에서의 필요 레벨의 최대값을 저장해주고,
      max_level = max(level, new_level)
      # 만약 그 레벨이 그 위치에서의 누적 최소 레벨보다 작을 경우
      if max_level < dp[new_dest]:
        # 그 누적 최소 레벨에 해당 최대 레벨을 담아준다.
        dp[new_dest] = max_level
        # 그리고 새로운 목적지에 새로운 필요 최소 레벨을 갱신해준 후 담아준다.
        queue.append([new_dest, max_level])

  # 마지막 위치에 누적 계산을 통해 저장된 필요 최소 레벨을 출력해준다.
  return dp[-1]

# 다익스트라를 통해 체육관 1부터 계산을 다 돌려주어
# 필요한 최소 레벨을 계산해준다.
min_level = dijkstra(1)

# 소수인지를 확인해주는 코드 (조건 : num >= 2 여야 함.)
# 소수의 의미: 숫자 num이 있을 때, 1과 num을 제외하고 나눗셈의 나머지가 0인 수가 없어야 함.
def b_prime(num):
  for i in range(2, int(math.sqrt(num))+1):
    if (num % i == 0):
      return False
  return True

# 포켓몬의 최소 레벨은 체육관 최소 요구 레벨보다 높아야 한다.
for i in range(min_level+1, 2*min_level):
  # 최소 요구 레벨이 0~1이라면 2를 출력.
  if (min_level <= 1):
    print(2)
    break
  else:
    if (b_prime(i)):
      print(i)
      break

 

 

결과