[Algorithm][python3][BOJ 9019] DSLR

문제

 

문제 링크 : https://www.acmicpc.net/problem/9019

9019번: DSLR

네 개의 명령어 D, S, L, R을 사용하는 간단한 계산기가 있다.

계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다.

각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다.

n의 네 자릿수를 d1, d2, d3, d4라고 하자.

1. D : n을 두 배로 바꾼다. 결과가 9999보다 크면 10000으로 나눈 나머지를 취한다.

2. S : n - 1을 레지스터에 저장한다. 만약 n이 0이라면 9999가 대신 저장된다.

3. L : n의 각 자릿수를 왼편으로 회전시킨다. 즉, 왼편부터 d2, d3, d4, d1이 된다.

4. R : R은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 즉, 왼편부터 d4, d1, d2, d3이 된다.

 

서로 다른 두 정수 A, B가 입력되었을 때 A를 B로 바꾸는 최소한의 명령어를 생성하여 출력하시오.

 

 

풀이

 

주어진 수에 대해 모든 연산을 실행하여 정답을 찾는 완전 탐색 문제이다.

핵심 알고리즘은 BFS. 최소한의 명령어를 사용한다는 규칙 << 에서 BFS를 떠올려야 한다.

 

방문 표시를 할 배열은 연산으로 될 수 있는 모든 수를 담아야 한다.

즉 visited = [10000] * false로 초기화한다.

queue는 레지스터값, 명령어가 저장된다. 처음엔 A와 빈 문자열로 초기화한다.

queue가 빌 때까지 while 문을 돌며, 만약 queue에서 꺼낸 값이 최종값과 같을 경우 종료한다.

D, S, L, R을 각각 수행한 후 나온 수를 방문했다고 하고, queue에 이전 수행한 값과 함께 저장한다.

 

(처음엔 이해가 안되서 한번 문제의 예시를 가지고 시뮬레이션을 돌려보았다...)

문제의 예시와 같이 A는 1234, B는 3412라고 가정하자.

1) queue = [(1234, "")] -> pop -> (1234, "")

D -> 2468 -> 2468 방문, queue = [(2468, "D")]

S -> 1233 -> 1233 방문, queue = [(2468, "D"), (1233, "S")]

L -> 2341 -> 2341 방문, queue =  [(2468, "D"), (1233, "S"), (2341, "L")]

R -> 4123 -> 4123 방문, queue = [(2468, "D"), (1233, "S"), (2341, "L"), (4123, "R")]

 

2) queue = [(2468, "D"), (1233, "S"), (2341, "L"), (4123, "R")] -> pop -> (2468, "D")

D -> 4936 -> 4936 방문, queue = [(1233, "S"), (2341, "L"), (4123, "R"), (4936, "DD")]

S -> 2467 -> 2467 방문, queue =  [(1233, "S"), (2341, "L"), (4123, "R"), (4936, "DD"), (2467, "DS")]

L -> 4682 -> 4682 방문, queue =  [(1233, "S"), (2341, "L"), (4123, "R"), (4936, "DD"), (2467, "DS"), (4682, "DL")]

R -> 8246 -> 8246 방문, queue =  [(1233, "S"), (2341, "L"), (4123, "R"), (4936, "DD"), (2467, "DS"), (4682, "DL"), (8246, "DR")]

....

.... 이렇게 저장될 것이다.

queue안에 든 명령어는 처음엔 길이가 1였다가 while문이 진행될 수록 뒤에 명령어가 붙으면서 계속 늘어난다.

그 때마다 방문했는지를 체크해서 방문한 곳을 또 방문하게 되었을 경우엔 queue에 넣지 않음으로 최선의 경우일 때만 나온다.

원하는 결과값이 LL이 나올 때는 아마도 이렇게

..) queue = [(2341, "L"), (4123, "R").........] -> pop -> (2341, "L")

D -> 4682 -> 2번에서 방문했으므로 처리X

S -> 2340 -> 2340 방문, queue =  [(4123, "R"), (4936, "DD"), ... , (2340, "LS")]

L -> 4682 -> 4682 방문, queue = [(4123, "R"), (4936, "DD"), ... , (2340, "LS"), (3412, "LL")]

R -> 8246 -> 8246 방문, queue = [(4123, "R"), (4936, "DD"), ... , (2340, "LS"), (3412, "LL"), (1234, "LR")]

일 것이고, LL 앞의 모든 queue 안에 든 값이 빠지고 나서야 3412가 확인되고, 함수가 종료될 것이다.

 

Python 코드

 

from collections import deque
import sys

input = sys.stdin.readline

def D(n) : # n을 두배로 바꿈
  res = 2 * n
  if res > 9999 :
    res %= 10000
  return res

def S(n) : # n - 1
  res = n - 1
  if res == -1 :
    res = 9999
  return res

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

def R(n) : # 오른쪽으로 회전 : 1234 -> 4123
  front = n % 10
  back = n // 10
  res = front * 1000 + back
  return res
  
def bfs(a, b) :
  def check(reg_anything, chr) : # visited 체크 및 queue에 append
    if not visited[reg_anything] :
      visited[reg_anything] = True
      queue.append((reg_anything, command + chr))
      
  visited = [False] * 10000
  queue = deque()
  queue.append((a, '')) # (레지스터값, 누적된 명령어)

  while queue :
    register, command = queue.popleft()
    if register == b : # resister가 b일 때
      return command
    reg_D = D(register)
    check(reg_D, 'D')
    reg_S = S(register)
    check(reg_S, 'S')
    reg_L = L(register)
    check(reg_L, 'L')
    reg_R = R(register)
    check(reg_R, 'R')
    
  
t = int(input()) # 테스트 케이스 갯수 입력
for i in range(t) :
  a, b = map(int, input().split(' '))
  print(bfs(a, b))

 

 

 

후기 및 보완할 점

 

해당 문제는 python3으로 제출하면 시간 초과가 나서 pypy3으로 제출했다.

pypy3으로 하지 않고도 해결할 수 있는 방법이 있을까?