[탐색/BFS] 백준 9019 DSLR - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

9019번: DSLR

 

 

 

2. 문제 풀이

D: (N*2) % 10000
S: N-1, 단 0이면 9999
L: 왼쪽으로 회전
R: 오른쪽으로 회전

 

 최소의 DSLR 연산으로 A가 B가 되도록 만드는 문제입니다. 개인적으로 DP로도 풀 수 있을 거 같은데, 중복되는 수가 많이 안 나올 거 같아서 효율은 보장 못하겠네요.

 

2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

[Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

 D, S, L, R을 균등하게 탐색해야 하므로, BFS탐색 문제입니다. 그래야 B를 찾았을 때, 최소의 연산과정을 출력할 수 있습니다.

 

D
S
L
R
DD
DS
DL 
...

 이런 식으로 찾아야 하므로 DFS탐색으로는 구하기 어렵습니다.

 

 

 

3. 코드

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

#입력
T = int(input())
for _ in range(T):
    A, B = map(int, input().split())

    #bfs탐색
    queue = deque([(A,'D'), (A,'S'), (A,'L'), (A,'R')])
    while queue:
        n, x = queue.popleft() #숫자, 연산

        #DSLR 연산
        if x[-1] == 'D':
            n = (n*2) % 10000
        elif x[-1] == 'S':
            n -= 1
            if n == -1:
                n = 9999
        elif x[-1] == 'L':
            thousand = n//1000 #천의 자리
            n = (n%1000)*10 + thousand #천의 자리를 떼서 뒤에 붙임
        else:
            one = n % 10 #일의 자리
            n = n//10 + one*1000 #일의 자리를 떼서 앞에 붙임

        #B와 같아졌다면 BFS탐색 종료
        if n == B:
            print(x)
            break

        #아니라면 계속 진행
        queue.append((n, x + 'D'))
        queue.append((n, x + 'S'))
        queue.append((n, x + 'L'))
        queue.append((n, x + 'R'))

 DSLR 4가지 연산을 구현하고, 순서대로 BFS 탐색합니다. 예제는 문제없이 잘 나오지만 메모리 초과가 뜹니다.

 처음에는 1 ~ 10000까지고, 마주칠 일이 없는 4가지 연산 같아서 '방문 여부'를 체크 안 했습니다. 하지만 어림없이 메모리 초과군요.

 

 

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

#입력
T = int(input())
for _ in range(T):
    A, B = map(int, input().split())

    #bfs탐색
    visit = [False]*10000
    queue = deque([(A,'D'), (A,'S'), (A,'L'), (A,'R')])
    while queue:
        n, x = queue.popleft() #숫자, 연산
        visit[n] = True #방문

        #DSLR 연산
        if x[-1] == 'D':
            n = (n*2) % 10000
        elif x[-1] == 'S':
            n -= 1
            if n == -1:
                n = 9999
        elif x[-1] == 'L':
            thousand = n//1000 #천의 자리
            n = (n%1000)*10 + thousand #천의 자리를 떼서 뒤에 붙임
        else:
            one = n % 10 #일의 자리
            n = n//10 + one*1000 #일의 자리를 떼서 앞에 붙임

        #B와 같아졌다면 BFS탐색 종료
        if n == B:
            print(x)
            break

        #방문한 숫자가 아니라면 탐색 진행
        if not visit[n]:
            queue.append((n, x + 'D'))
            queue.append((n, x + 'S'))
            queue.append((n, x + 'L'))
            queue.append((n, x + 'R'))

 방문 여부를 체크해서, 방문한 숫자에는 탐색하지 않습니다. 하지만 이 코드는 시간초과가 납니다.

 

 

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

#입력
T = int(input())
for _ in range(T):
    A, B = map(int, input().split())

    #bfs탐색
    visit = [False]*10000
    queue = deque([(A, "")])
    visit[A] = True
    while queue:
        n, x = queue.popleft() #숫자, 연산

        # B와 같다면 BFS탐색 종료
        if n == B:
            print(x)
            break

        #아니라면 DSLR 연산
        #D연산
        num = (n*2) % 10000
        if not visit[num]:
            visit[num] = True #방문
            queue.append((num, x + 'D'))

        #S연산
        num = (n-1) if n != 0 else 9999 #n-1, 단 0이면 9999
        if not visit[num]:
            visit[num] = True #방문
            queue.append((num, x + 'S'))

        #L연산
        num = (n%1000)*10 + n//1000 #천의 자리를 떼서 뒤에 붙임
        if not visit[num]:
            visit[num] = True #방문
            queue.append((num, x + 'L'))

        #R연산
        num = n//10 + (n%10)*1000 #일의 자리를 떼서 앞에 붙임
        if not visit[num]:
            visit[num] = True #방문
            queue.append((num, x + 'R'))

 if문을 줄일 수 있을만큼 줄였습니다. 그제서야 pypy3로 겨우 통과가 되었습니다. 쉽지 않군요..