[BOJ 백준] 9019번 : DSLR (Python, 파이썬)

www.acmicpc.net/problem/9019

9019번: DSLR

 

 

카테고리 분류에 BFS가 있어서 당황했던 문제이다. 

이런류의 문제를 BFS에 접목시킨다는 발상을 하기가 어렵다. 실제 코테에 나왔다면 못풀었을 것이다.

 

 

 

어려웠고 놓쳤던 부분은 다음과 같다.

• '123' 을 R 연산하면 312가 아니라, '2031'이된다. 숫자는 무조건 4자리로 고정되어있기 때문이다.
• 숫자 하나당 4가지의 경우의 수가 발생해서 4^n 만큼의 경우의 수가 나올 거 같은데, 어떻게 시간 내에 풀어야 할지

두 개 모두 질문검색에 올라온 글들을 참고하여 해결했다. 

 

 

 

또한 다음의 이유로 시간초과가 발생했다.

• 방문체크를 하는 visited를 list로 만들었다.
• L, R 연산을 숫자로 연산하지 않고 문자열로 바꾼뒤 숫자를 이동시킨 후 다시 정수형으로 바꿔서 리턴했다.

list에서 in을 사용한 원소 탐색은 시간복잡도가 O(n)이다. visited를 list가 아닌 set으로 만들면 원소 탐색에 시간복잡도가 O(1)이 걸린다. 

또 다른 방법으로는 visited 배열을 길이가 10000인 list로 초기화 시켜서 visited[찾으려는 숫자]의 방법으로 할 수 있다.

 

 

원래 작성했던 L, R 연산의 코드는 아래와 같다. 

  def oper_L(n): # 왼쪽으로 회전 : 1234 -> 2341
      tmp = str(n)
      res = tmp[1:]
      res += tmp[0]    
      return int(res)


  def oper_R(n): # 오른쪽으로 회전 : 1234 -> 4123    
      res = str(n)[-1::-1]   
      return int(res)

 

 

해당 문제의 질문검색을 보니 문자열로 변환하고 다시 정수형으로 변환하는 과정에서 걸리는 시간 때문에 시간초과가 걸린다는 말이 있어서 아래와 같이 문자열로 변환하지 않고 숫자 연산으로 계산해주었다.

  def oper_L(n): # 왼쪽으로 회전 : 1234 -> 2341    
      front = n % 1000
      back = n // 1000
      res = front*10 + back
      return res


  def oper_R(n): # 오른쪽으로 회전 : 1234 -> 4123  
      front = n % 10
      back = n // 10
      res = front*1000 + back

 

 

 

소스코드

  import sys
  from collections import deque
  #sys.stdin = open("input.txt","r")

  def oper_D(n): # D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
      res = n * 2
      if res > 9999:
          res %= 10000    
      return res

  def oper_S(n): # S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
      res = n
      if res == 0: return 9999
      res -= 1
      return res


  def oper_L(n): # 왼쪽으로 회전 : 1234 -> 2341    
      front = n % 1000
      back = n // 1000
      res = front*10 + back
      return res


  def oper_R(n): # 오른쪽으로 회전 : 1234 -> 4123  
      front = n % 10
      back = n // 10
      res = front*1000 + back
      return res

  def go(s, t):
      queue = deque()
      visited = set() # logn
      queue.append((s, "")) 
      visited.add(s)
      while queue:
          cur_num, oper = queue.popleft()
          if cur_num == t:
              print(oper)            
              return        
          tmp = oper_D(cur_num)        
          if tmp not in visited:
              visited.add(tmp)
              queue.append((tmp, oper+"D"))

          tmp = oper_S(cur_num)
          if tmp not in visited:
              visited.add(tmp)
              queue.append((tmp, oper+"S"))      

          tmp = oper_L(cur_num)
          if tmp not in visited:
              visited.add(tmp)
              queue.append((tmp, oper+"L"))

          tmp = oper_R(cur_num)
          if tmp not in visited:
              visited.add(tmp)
              queue.append((tmp, oper+"R"))

  for _ in range(int(input())):
      start, target = map(int, input().split()) 
      #print(start, target)  
      go(start, target)