[bfs/백준] 9019번 : DSLR

- 문제 : https://www.acmicpc.net/problem/9019

 

문제 이해

- 조건 D, S, L, R에 따라 숫자를 계산한 뒤 타겟 숫자까지 최소 몇 번의 연산으로 갈 수 있는지 출력하는 문제다.

- 이전에 풀었던 bfs 문제들처럼 조건으로 탐색한 뒤 queue를 이용하는 방식으로 구현했는데, 계속 시간초과가 발생했다.

- 찾아보니까 탐색할 때 분기문이 너무 많아지면 시간이 오래걸릴 수 있다고 한다. 그래서 미리 숫자들을 계산한 뒤 각 케이스를 for문 탐색으로 진행하는 것이 아닌 단일 분기문으로 처리하면 통과한다.

- python으로는 시간초과가 발생해서 pypy3로 진행했다.

 

풀이 로직

- 시작 숫자(a)와 타겟 숫자(b)를 입력 받는다.

- bfs 진행 할 queue와 중복 숫자 방문을 방지하기 위한 visit 배열을 초기화한다. 

queue는 [숫자, 그 숫자까지의 연산 문자들] 원소로 이뤄져있고, visit[숫자] = 1은 숫자를 이전에 방문했다는 표시이다.

- while문으로 bfs를 진행하면서 타겟을 찾은 경우 문자열을 출력한 뒤 while문을 break 한다

- 조건 D, S, L, R에 맞는 숫자들 dd, ds, dl, dr을 계산한 뒤 각 케이스별로 방문하지 않은 숫자이면 방문처리 후 탐색을 마저 진행하면 된다.

정답 풀이

분기문 줄일 수 있게 미리 숫자 계산하기

dd, ds, dl, dr은 모두 한번의 연산으로 진행하는 것이 빠름 + dl, dr은 문자열이 아니라 수학으로 풀자

from collections import deque

for _ in range(int(input())):
    a, b = map(int, input().split())
    
    queue = deque()
    queue.append([a, ''])
    visit = [0] * 10000
    visit[a] = 1
    while queue:
        x, words = queue.popleft()
        
        if x == b :
            print(words)
            break
        
        dd = 2 * x % 10000
        ds = (x - 1) % 10000
        dl = x // 1000 + (x % 1000) * 10
        dr = x // 10 + (x % 10) * 1000
        if not visit[dd]:
            visit[dd] = 1
            queue.append([dd, words + 'D'])
            
        if not visit[ds]:
            visit[ds] = 1
            queue.append([ds, words + 'S'])
        
        if not visit[dl]:
            visit[dl] = 1
            queue.append([dl, words + 'L'])
            
        if not visit[dr]:
            visit[dr] = 1
            queue.append([dr, words + 'R'])