백준 9019 DSLR

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/9019

풀이

난이도 : Gold IV

이 문제는 D, S, L, R 이라는 네 가지 연산이 있는데, 입력받은 두 숫자 a, b에 대하여 연산들을 잘 조합해서 최소한의 명령어를 사용하여 a를 b로 만들면 되는 문제이다.

✔ 이 문제에서 생각해봐야 할 점은 문제를 푸는 방법과 연산을 할 때 주의할 점이다.

우선 문제를 푸는 방법은 bfs를 사용하였다.

1) 처음에 a라는 숫자를 queue에 넣어두고, 방문했다고 표시 (visited = True)
2) 반복문을 사용하여 queue가 비어있을 때까지 반복하여 bfs를 진행
3) queue에서 값을 pop하여 그 숫자에 대한 D, S, L, R 연산을 수행하고 각 결과에 대해 visited 처리를 한 후에, q에 값을 넣어준다.
4) 3)에서 queue pop을 할 때마다 b와 같은 숫자인지 비교 후 같을 경우 결과 출력 후 break

✔ 주의할 점

• 연산자 L과 R은 자릿수 이동 연산인데, 2진수 비트연산자를 십진수에 한다고 이해하면 된다.

• 또한 네 자리 숫자가 아니더라도 빈 자리 수는 0으로 채워져있다고 생각하여야 한다.

• 문제를 보고 오해하면 안되는 부분 예시
  L :
  123 -> 312 x
  123 -> 3012 o

  R :
  123 -> 231 x
  123 -> 1230 o

✔ 참고

• python에서 이 문제와 같이 list로 되어 있는 결과를 string으로 연결하여 출력할 경우에 .join()을 사용하면 쉽게 구현할 수 있다.
• python으로 이 문제를 백준에 제출할 경우 python3는 시간 초과가 나오므로, pypy3로 제출해야 한다.

코드

from collections import deque

def getDSLR(x):
    dslr = []
    
    # DSLR
    dslr.append((x * 2) % 10000)
    dslr.append(x - 1 if x != 0 else 9999)
    dslr.append((x * 10) % 10000 + (x * 10) // 10000)
    dslr.append((x % 10) * 10000 // 10 + (x // 10))

    return dslr

def main():
    t = int(input())

    # DSLR 문자
    dslr_str = ["D", "S", "L", "R"]

    for _ in range(t):
        a, b = map(int, input().split())

        # bfs 사용 : visited, deque 설정
        visited = [False] * (10001)
        q = deque()
        visited[a] = True
        q.append((a, []))

        while q:
            a, results = q.popleft()
            
            if a == b:
                print(''.join(results))
                break
            
            dslr = getDSLR(a)

            for i in range(len(dslr)):
                if not visited[dslr[i]]:
                    visited[dslr[i]] = True
                    q.append((dslr[i], results + [dslr_str[i]]))

if __name__ == "__main__":
    main()