[BOJ] 9019. DSLR

www.acmicpc.net/problem/9019

9019번: DSLR

 

문제: DSLR이라는 4가지 명령어로 주어진 숫자를 목표값으로 최소한의 명령을 통해 바꾸어라.

 

문제 이해하기!!

아, 이 문제 너무 깐깐한 문제였습니다.

문제에 테스트케이스의 수가 나와있지 않고 시간제한이 6초라니....

일단 알아본봐로는 테케 수가 최대 1만개라고 합니다! 참고^^

이 문제를 풀려면 BFS 방법을 써야하는데요, 일단 4가지 명령어는 쉽게 구현됩니다.

하지만 여기서 DFS를 써버리면 시간초과가 나오게 되니 조심하세요... ㅎ

(시간초과 이유: 시간이 깐깐한 문제에다가 정답이 여러 개에 최소 명령어 수를 구하는 것이기 때문)

 

제가 푼 방식을 설명하자면,

1. visit배열을 만들어서 10000까지 방문체크를 합니다.

2. BFS구현: 큐에 입력받은 초기 숫자를 넣고 팝하여, 팝한 수를 각 명령어를 한번씩 수행하고 다시 큐에 넣습니다.

3. 2번을 반복하다가 목표 숫자와 같아지면 해당 명령어들을 나열하면 됩니다.

 

사실 저는 처음에 무지성으로 DFS로 풀었다가 시간초과, 메모리초과 다 나서 다시 BFS로 바꿔서 풀었는데,

S 명령어에서 n==0일때 9999로 바꾸라는 말이 변환 후에 0이되면 9999로 바꾸라는 말인줄 알고

입력되는 값이 1일때 9999로 바꾸는 코드를 찾느라고 시간을 쏟아부었습니다.. ㅎ;;

저처럼 되지 않길 바랄게요 ㅠㅠ

밑에는 제가 짠 코드입니다.

 

코드:

from collections import deque
from sys import stdin
input = stdin.readline

def dslr(x):
    Q = deque([(x, "")])
    while Q:
        nx, res = Q.popleft()
        if nx == b:
            return res
        if visit[nx]:
            continue
        visit[nx] = True
        ne = (nx*2)%10000
        if visit[ne] == False:
            Q.append((ne, res + "D"))
        ne = (nx - 1) % 10000
        if visit[ne] == False:
            Q.append((ne, res + "S"))
        ne = ((nx * 10) % 10000) + nx //1000
        if visit[ne] == False:
            Q.append((ne, res + "L"))
        ne = ((nx % 10) * 1000) + (nx // 10)
        if visit[ne] == False:
            Q.append((ne, res + "R"))

N = int(input())
for _ in range(N):
    a, b = map(int, input().split())
    visit = [False] * 10000
    print(dslr(a))