[백준]9019(파이썬) - DSLR

https://www.acmicpc.net/problem/9019

9019번: DSLR

 

• 이 문제는 보고 처음에 든 생각은 BFS 문제구나 싶었습니다. 항상 2중 리스트에서 상하좌우를 고려해서 풀어나가는 방식의 BFS 문제를 많이 접했는데요, 익숙하지 않아서 BFS 문제라는 확신이 들기까지는 꽤 오래 걸렸죠.
• 이 문제에서 D, S, L, R 조건을 구현하는 건 어렵지 않았고, 이거 BFS인 거 알겠어? 를 물어보는 문제였습니다.
• 먼제 D, S, L, R 일 때 각각 다른 조건을 만족시켜주기 위해 order라는 함수를 만들어서 숫자와 문자를 변수로 받습니다. 그다음에는 문자가 D, S, L, R 일 때 각각 조건을 만족시켜준 뒤 return을 하면 되죠. L, R 같은 경우에는 처음에 deque.rotate() 함수로 구현하려고 했지만 오히려 더 직관적인 풀이가 좋을 것 같아서 아래와 같이 구현했습니다.
• 다음은 다른 BFS 문제와 유사합니다. q를 만들어주고, 방문처리를 하는 과정을 거치죠.
• 이 문제에서 핵심은 가능한 경우(방문을 안했을 경우)에 D, S, L, R을 통해서 바뀐 숫자와 현재 문자에 가능한 경우의 문자를 붙여서 q에 넣어줘야 하는 것입니다.
• 10000개밖에 없다고 했으니, visited는 10000으로 초기화 해주면 되겠죠?
• 자세한 설명은 주석을 참고해주시면 감사하겠습니다.

 

#  이문제는 dfs문제인거 같다.
import sys
input = sys.stdin.readline
from collections import deque


t = int(input())

def order(num, case):
    if case == 'D':
        # n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 
        # 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
        return (int(num) * 2) % 10000
    elif case =='S':
        # n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
        return (int(num)-1) % 10000
    elif case == 'L':
        # n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 
        # 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
        tmp = num // 1000
        return num % 1000 * 10 + tmp
    elif case == 'R':
        # n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 
        # 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.
        tmp = num % 10
        return num // 10 + 1000 * tmp

# for문을 돌아서 다음 경우를 확인 해줄 리스트 
# 일반 BFS 문제에서 dx,dy 역할
d = ['D','S','L','R']

def bfs(a,b,visited):
    # a와 빈 문자열을 q에 넣어주고 시작.
    q = deque([[a,""]])
    # a 는 방문처리
    visited[a] = 1
    # BFS 시작
    while q:
        num, case = q.popleft()
        if num == b:
            print(case)
            break
        # 현재숫자에서  D,S,L,R 을 적용해보고 가능한 숫자를 구해준다.
        for i in range(4):
            n_case = order(num,d[i])
            if visited[n_case] == 0:
                # 가능한 숫자가 있다면, 가능한 숫자와 가능하게 한 문자를 처음 "" 로 시작한 문자열 뒤에 붙여준다.
                q.append((n_case,case+d[i]))
                visited[n_case] = 1

for _ in range(t):
    # 조건에서  10000 미만이라고 했으니, 10000으로 초기화 해준다.
    visited=[0 for _ in range(10000)]
    a,b = map(int,input().split())
    bfs(a,b,visited)