[백준BOJ] 9019번 DSLR.py

 

백준 저지에서 DSLR을 파이썬을 통해 풀어 보았다. 

 

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

9019번: DSLR

 

9019번 DSLR.py

tomy9729/Algorithm

 

9019번 DSLR

문제

네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자)

- D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
- S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
- L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
- R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.

위에서 언급한 것처럼, L 과 R 명령어는 십진 자릿수를 가정하고 연산을 수행한다. 예를 들어서 n = 1234 라면 여기에 L 을 적용하면 2341 이 되고 R 을 적용하면 4123 이 된다.
여러분이 작성할 프로그램은 주어진 서로 다른 두 정수 A와 B(A ≠ B)에 대하여 A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램이다. 예를 들어서 A = 1234, B = 3412 라면 다음과 같이 두 개의 명령어를 적용하면 A를 B로 변환할 수 있다.
1234 →L 2341 →L 34121234 →R 4123 →R 3412
따라서 여러분의 프로그램은 이 경우에 LL 이나 RR 을 출력해야 한다.
n의 자릿수로 0 이 포함된 경우에 주의해야 한다. 예를 들어서 1000 에 L 을 적용하면 0001 이 되므로 결과는 1 이 된다. 그러나 R 을 적용하면 0100 이 되므로 결과는 100 이 된다.

설명

처음에는 재귀함수나 브루트 포스로 문제를 풀까 했지만 그런 식으로는 시간 초과를 피할 수 없을 것 같았다. 레지스터에 저장되는 숫자의 범위가 0~9999이기 때문에 BFS를 통해 문제를 해결했다.

 

각 연산 D,S,L,R을 수행하는 함수 DSLR을 구현했다. 명령어에 따라 n을 연산하며 연산 결과를 반환한다.

 

다음으로 BFS를 구현했다. 시작 지점은 a이며 큐에서 빼낸 숫자가 b라면 while문을 종료한다. 0~9999 사이의 숫자가 무조건 나오기 때문에 예외처리는 하지 않았다. 

 

visit은 최초에는 전부 -1로 저장하며 이후에는 a에서 해당 숫자까지의 연산 과정을 저장했다. 만약 visit이 -1이라면 아직 방문하지 않았으므로 방문을 시도하고 연산 과정을 저장한다. 아직 방문하지 않은 숫자로만 연산을 수행함으로써 시간 초과를 회피할 수 있다.

 

단 pypy3로 컴파일했을 때만 정답으로 인정되고 python3로 컴파일하면 시간 초과가 발생한다. 맞은 사람을 확인해보니 python3로 문제를 맞힌 사람이 3명밖에 없는걸 보면 아예 다른 공략법이 존재하는 것 같다.

 

DP로도 문제를 해결할 수 있을 것으로 보인다. 다만 BFS로 푸는 방법이 먼저 떠올라서 BFS로 풀었다.

코드

#9019번 DSLR
from collections import deque
def DSLR(n, ins) : 
  d1 = n//1000
  d2 = (n-d1*1000)//100
  d3 = (n-d1*1000-d2*100)//10
  d4 = n-d1*1000-d2*100-d3*10
  if ins == "D" : 
    n = 2*n %10000
  elif ins == "S" : 
    if n==0 : 
      n = 9999
    else : 
      n -= 1
  elif ins == "L" : 
    n = d2*1000+d3*100+d4*10+d1
  elif ins == "R" : 
    n = d4*1000+d1*100+d2*10+d3
  return n

def BFS(a,b,visit):
  visit[a] = ""
  q = deque()
  q.append(a)
  instruction = ["D","S","L","R"]
  while q:
    now = q.popleft()
    if now == b : 
      return visit[now]
    for ins in instruction : 
      next = DSLR(now,ins)
      if visit[next] == -1 : 
        visit[next] = visit[now]+ins
        q.append(next)

if __name__ == "__main__":
  t = int(input())
  for _ in range(t) : 
    a,b = map(int,input().split())
    visit = [-1]*10000
    print(BFS(a,b,visit))