leah

my dev_log

0%

BOJ 9019

Posted on In ,

Input

프로그램 입력은 T 개의 테스트 케이스로 구성된다. 테스트 케이스 개수 T 는 입력의 첫 줄에 주어진다.

각 테스트 케이스로는 두 개의 정수 A와 B(A ≠ B)가 공백으로 분리되어 차례로 주어지는데 A는 레지스터의 초기 값을 나타내고 B는 최종 값을 나타낸다. A 와 B는 모두 0 이상 10,000 미만이다.

1
2
3
4
5
6
7
from collections import deque
import sys
input = sys.stdin.readline
t = int(input())

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

BFS

이 문제 접근 방식의 핵심은 가능한 숫자 0~9999의 index로 이루어진 visited 배열을 선언하고, dslr 4가지 경우를 체크하여 visited를 체크하는 것이다.

처음에는 무작정 4가지 경우의 수를

  • 이미 있는 숫자의 위치만 바꾸면 되는 경우: L, R
  • 그 외, 현재 숫자에 최종 숫자의 수가 없는 경우: D, S

로 나누어서 BFS로 풀었는데, 메모리 초과가 나버렸다. 그럴 수 밖에 없는게, DSLR 모든 경우를 매번 가능할 때마다 큐에 append 했기 때문..

진짜 많이 사용되는 방법이기 때문에 익혀두면 좋을 거다! 특히 숫자, 알파벳의 방문 여부를 체크하는 문제는 이 방식처럼 애초에 그를 이용해서 배열을 생성해놓으면 된다.

이것만 파악하면 코딩은 쉬움. (코드가 좀 귀엽다… ^.6..)

1
2
3
# arr에 방문 시 체크하면, 더 빨리 체크한 dslr 케이스가 진행된다.
arr = [0]*10000
print(bfs(a, b))

  • dslr의 모든 조건을 체크하고, 만족하는 케이스를 큐에 넣어서 정답을 만날 때 break, 아니면 계속 모든 경우 체크 + 이어나가기 + breakpoint 체크를 반복하기 때문에 BFS이다.

  • 큐 내의 조건문은 주어진 DSLR 조건에 따라 코딩하면 됨. 👈 코드가 귀엽다구.. 처음 시도했던 방식에서 디버깅 하느라 죽는 줄 알았는데, 정답이 귀여우니까 참내,, ^^

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    def bfs(a, b):
      q = deque()
      q.append((a, ""))

      while q:
        n, dslr = q.popleft()

        dn = 2 * n % 10000
        if dn == b: return dslr+"D"
        if not arr[dn]:
          arr[dn] = 1
          q.append((dn, dslr+"D"))
        sn = n - 1 if n != 0 else 9999
        if sn == b: return dslr+"S"
        if not arr[sn]:
          arr[sn] = 1
          q.append((sn, dslr+"S"))
        ln = int(n % 1000 * 10 + n // 1000)
        if ln == b: return dslr+"L"
        if not arr[ln]:
          arr[ln] = 1
          q.append((ln, dslr+"L"))
        rn = int(n % 10 * 1000 + n // 10)
        if rn == b: return dslr+"R"
        if not arr[rn]:
          arr[rn] = 1
          q.append((rn, dslr+"R"))

Output

A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다. 가능한 명령어 나열이 여러가지면, 아무거나 출력한다.

가능한 게 여러가지인데 아무거나 출력하라고 하면 그냥 정답 찾을 때 return 하면 된다. 다 출력하라고 하지 않는 이상 신경 안 써도 됨.

1
print(bfs(a, b))