백준12851 - 숨바꼭질2 (DP) Python

https://www.acmicpc.net/problem/12851

문제는 첫 번째, 두 번째 입력값을 각각 n,m 이라고 하고

n은 한번의 연산으로 n - 1 | n + 1 | n * 2 로 바꿀 수 있을 때 m 이 되기 위한 최소 횟수를 구하는 문제다.

해당 문제의 유형은 너비우선탐색으로 분류되어 있었지만, 다이나믹 프로그래밍으로 풀이하듯 접근했다.

 

처음 작성한 코드

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read()

def solution (data) :
  n,m = map(int,data.split())
  dp = [[n]]
  idx = 0
  while not m in dp[idx] :
    temp = []
    dupTemp = {}
    for v in dp[idx] :
      arr = [v - 1, v + 1, v * 2]
      for j in arr :
        if verify(j) :
          temp.append(j)
          dupTemp[j] = True
    dp.append(temp)
    idx += 1
  
  print(idx)
  print(len([v for v in dp[idx] if v == m]))

def verify (n) :
  return 0 <= n <= 100000
  
  
solution(input_data)

 

처음 풀이 방식은 해당 연산으로 나올 수 있는 모든 경우를 메모라이징하며 m이 나올 때까지 연산을 진행했는데,

연산을 진행할수록 메모라이징해야 할 데이터의 양이 커지다보니 메모리 초과 문제로 오답을 받았다.

 

이 문제로 내가 작성한 코드를 살피다,

현재 연산에서 중복으로 나온 수가 아닌, 이전 연산에서 나왔던 수가 중복으로 나타날 경우

이에 대해 중복처리를 해주면 해결된다는 것을 깨닫고 수정했다.

 

즉, n = 1, m = 4 이라고 했을 때 연산 과정을 그래프로 나타내면 아래와 같은데,

붉은 색으로 표시된 연산만 제거해도 불필요한 메모라이징을 제거하면서 연산의 경우의 수를 메모라이징 할 수 있다는 것.

(이때 보라색은 -1 로 0 이상 && 100000 이하가 아닌 범위밖의 수)

 

수정한 전체 소스 코드

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read()

def solution (data) :
  n,m = map(int,data.split())
  dp = [[n]]
  dupTable = {n:True} # 중복 저장
  idx = 0
  while not m in dp[idx] :
    temp = []
    dupTemp = {}
    for v in dp[idx] :
      arr = [v - 1, v + 1, v * 2]
      for j in arr :
        if verify(j) and not dupTable.get(j,None): # 중복 검증
          temp.append(j)
          dupTemp[j] = True # 중복 추가
    dp.append(temp)
    dupTable.update(dupTemp) # 중복 업데이트
    idx += 1

  print(idx)
  print(len([v for v in dp[idx] if v == m]))

def verify (n) :
  return 0 <= n <= 100000


solution(input_data)