[BOJ] 9019 : DSLR [DFS/BFS](Python)

문제 링크

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

9019번: DSLR

소스 코드

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

for _ in range(int(input())):
    a,b = map(int,input().split())
    q = deque()
    q.append((a,"")) # 변경 전,경로
    visit = [False] * 10000 # 방문 리스트 초기화
    
    while q:
        cur, path = q.popleft()
        visit[cur] = True
        if cur == b:
            print(path)
            break
        
        # D,2배로 바꾸기
        next = (2*cur) % 10000
        if not visit[next]:
            q.append((next,path+"D"))
            visit[next] = True
        # S,1빼기
        next = (cur-1) % 10000
        if not visit[next]:
            q.append((next,path+"S"))
            visit[next] = True
        # L,왼쪽으로 이동
        next = (10*cur + (cur//1000)) % 10000
        if not visit[next]:
            q.append((next,path+"L"))
            visit[next] = True
            
        # R,오른쪽으로 이동
        next = (cur//10 + (cur%10)*1000) % 10000
        if not visit[next]:
            q.append((next,path+"R"))
            visit[next] = True

 

해설

• BFS를 이용한 그래프 탐색
• python3 시간초과, pypy 통과

사실 풀이 방법이 떠오르지 않아서 다른 분이 풀이하신 좋은 코드를 가지고 왔다. 

BFS를 이용해서 탐색을 수행하는 아이디어도 좋고, 경로를 계속 업데이트하면서 최종값이 되었을 때 바로 출력할 수 있도록 큐에 추가하는 방식도 좋은 것 같다.

 

BFS 처리 과정

문제에서 주어진 명령 D,L,S,R을 하나씩 시도해 볼 수 있도록 되어 있다.

각 명령에 대해 수행이 가능한 상태이면 큐에 추가해서 명령 수행 이후를 기준으로 추가 탐색하도록 되어 있다.

 

큐에 추가할 때는 방문처리를 해서 이후 과정에서 중복되지 않도록 한다.

물론 D,S,L,R을 처리할 때 같은 결과가 나올 수도 있다.

예를 들어 1을 2배 하여 2가 나오는 것과 1에 1을 더하여 2가 나오는 것은 처리한 명령이 다르지만 결과는 같다.

 

이때 문제의 출력 조건을 보면 가능한 여러 명령 중 아무거나 출력하면 된다고 했기 때문에,

불필요한 연산을 생략하는 것으로 이해할 수 있다.

 

다시 말하면 굳이 D,S,L,R 순서로 검사하지 않아도 된다는 뜻이다.

 

 

왼쪽으로 이동, 오른쪽으로 이동

나머지 연산자를 이용하여 숫자를 적당히 조작한다.

# L,왼쪽으로 이동
next = (10*cur + (cur//1000)) % 10000

# R,오른쪽으로 이동
next = (cur//10 + (cur%10)*1000) % 10000

네 자리 숫자 1234를 예시로 생각해보자.

 

• L, 왼쪽으로 이동

10 * 1234 = 12340

1234 // 1000 = 1

12340 + 1 = 12341

12341 % 10000 = 2341

• R, 오른쪽으로 이동

1234 // 10 = 123

(1234 % 10) * 1000 = 4000

123 + 4000 = 4123

 

위 풀이 과정에서 볼 수 있듯 나머지 연산자와 몫 연산자를 적절히 조합하면,

숫자 전체를 왼쪽으로, 혹은 오른쪽으로 한 칸 밀 수 있게 된다.