BOJ(DSLR)(9019)

작성일 | In

DSLR 9019

  • 네 자리 숫자 A와 B가 주어졌을 때,

  • A->B로 바꾸는 최소 연산 횟수

  • D : N -> 2*N
  • S : N -> N-1
  • L : 한 자리씩 왼쪽으로

  • R : 한 자리씩 오른쪽으로

  • 최소 연산을 구하라.
  • 각각이 모두 연산 한번이므로 BFS로 풀이 가능

  • BFS로 풀 수 있는 문제라고 해도, 정점과 간선의 개수가 너무 많으면 BFS로 풀 수 없다.

  • 네자리 숫자라고 했기 때문에, 0000부터 9999까지 만개의 정점의 개수가 주어져 있다. -> BFS로 가능.
  • 최소 연산을 구하는데 어떻게 그걸 만들었는지 이 연산도 출력해야 한다.

  • 앞의 문제는 어디서 왔는지만 기록하면 되는데, 이 문제는 그 때 사용한 방법도 구해야 한다.

  • 배열을 하나 더 이용해서 어떤 과정을 거쳤는지를 저장해야 한다.
  • 첫 번째 방법은 기록하지 않고 계속 만든 방법을 살펴보며, 이걸 만든게 D인지 S인지 L인지 R인지 파악하는 것이며

  • 두 번째 방법은 how란 배열을 만들어서 사용한 연산을 넣어준다.

  • 그런데 어떻게 만들었는지를 모두 기록하면 안된다.
  • 모두 기록하면 공간이 매우 많이 필요하게 된다.
from collections import deque
import sys
MAX = 10001
sys.setrecursionlimit(MAX)
def go(n, m):
    if n == m:
        return
    go(n, via[m])
    print(how[m], end='')
t = int(sys.stdin.readline())
for _ in range(t):
    n,m = map(int,input().split())
    check = [False] * MAX
    dist = [-1] * MAX
    via = [-1] * MAX
    how = [''] * MAX
    check[n] = True
    dist[n] = 0
    via[n] = -1
    q = deque()
    q.append(n)
    while q:
        now = q.popleft()
        next = (now*2) % 10000
        if not check[next]:
            q.append(next)
            check[next] = True
            dist[next] = dist[now] + 1
            via[next] = now
            how[next] = 'D'
        next = now-1
        if next == -1:
            next = 9999
        if not check[next]:
            q.append(next)
            check[next] = True
            dist[next] = dist[now] + 1
            via[next] = now
            how[next] = 'S'
        next = (now%1000)*10 + now//1000
        if not check[next]:
            q.append(next)
            check[next] = True
            dist[next] = dist[now] + 1
            via[next] = now
            how[next] = 'L'
        next = (now//10) + (now%10)*1000
        if not check[next]:
            q.append(next)
            check[next] = True
            dist[next] = dist[now] + 1
            via[next] = now
            how[next] = 'R'

    go(n,m)
    print()

참고자료 codeplus

0%