mintchoco

(BOJ9019 DSLR

Link copied to clipboard

문제 설명

Link copied to clipboard
  • 하나의 숫자에서 시작해서 주어진 연산에 따라 가장 적은 연산을 찾는다.
  • 문제에서는 각 숫자로 연산 하는 것처럼 말하는데,
    • 실제로는 4자리를 기준으로 연산해야 하는 듯 하다.
    • 만약 5를 연산하면 실제로는 0005를 기준으로 생각해야한다, 특히 L, R 연산일 때 그렇다.

문제 풀이

Link copied to clipboard
A, B = map(int, input().split())
queue = deque([(A, "")])
check = [False] * 10001
while queue:
    x, now = queue.popleft()
    if x == B:
        print(now)
        break
    if check[x]:
        continue
    check[x] = True
    y = (x * 2) % 10000
    if not check[y]:
        queue.append((y, now + "D"))
    y = (x - 1) % 10000
    if not check[y]:
        queue.append((y, now + "S"))
    y = rotate_num(x, True)
    if not check[y]:
        queue.append((y, now + "L"))
    y = rotate_num(x, False)
    if not check[y]:
        queue.append((y, now + "R"))
  • 두 수를 입력 받고,
    • A에서 시작하여 BFS로 탐색한다.
  • D, L 연산은 크게 신경 쓸 필요 없지만, L, R 연산은 조금은 주의할 필요가 있다.
def rotate_num(x: int, left: bool) -> int:
    x = str(x).zfill(4)
    if left:
        x = x[1:] + x[0]
    else:
        x = x[-1] + x[:-1]
    return int(x)
  • L, R 연산은 위의 함수로 처리했고,
    • 문자열로 연산하여 처리했다.