9019. [Python]DSLR

1. 문제

 

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

9019번: DSLR

 

2. 접근 방법

 

• 시간 제한: 6초
• 메모리 제한: 256MB
• BFS(너비 우선 탐색)

 

3. 파이썬 코드

 

from collections import deque
import sys

input = sys.stdin.readline
# 2배 해주는 함수
def Double(num):
    return (num * 2) % 10000
# -1 해주는 함수
def Subtrack(num):
    return (num - 1) if num > 0 else 9999
# 너비우선탐색
def BFS(start, target):
    # 방문처리 체크
    visited = [False] * 10000
    # queue 에 값과 어떤 결과를 시행했는지 자정
    queue = deque([(start, "")])
    # 시작값 방문처리
    visited[start] = True
    # queue가 존재할 경우 계속 반복
    while queue:
        current, path = queue.popleft()
        # 2배 한 함수와 -1 한 함수 시행한 결과값 변수에 저장
        dobule_num = Double(current)
        subtrack_num = Subtrack(current)
        # left 로 움직이는 방법과 right로 움직이는 방법 변수에 저장
        left_num = (current % 1000) * 10 + (current // 1000)
        right_num = (current % 10) * 1000 + (current // 10)
        # 목표값과 같으면 현재 path + 각 연산을 결과를 출력
        if dobule_num == target:
            print(path + "D")
            return
        elif subtrack_num == target:
            print(path + "S")
            return
        elif left_num == target:
            print(path + "L")
            return
        elif right_num == target:
            print(path + "R")
            return
        # 저장된 숫자를 방문하지 않았을 경우 저장된 숫자 + 연산자를 queue에 추가해줌
        if not visited[dobule_num]:
            visited[dobule_num] = True
            queue.append((dobule_num, path + "D"))
        if not visited[subtrack_num]:
            visited[subtrack_num] = True
            queue.append((subtrack_num, path + "S"))
        if not visited[left_num]:
            visited[left_num] = True
            queue.append((left_num, path + "L"))
        if not visited[right_num]:
            visited[right_num] = True
            queue.append((right_num, path + "R"))

N = int(input())

for _ in range(N):
    problem, answer = map(int, input().split())
    BFS(problem, answer)

 

4. 문제를 풀고난 후 생각

 

• start, end 값이 주어져있으면 start를 통해서 2배, -1, 왼쪽이동, 오른쪽 이동한 값들을 각각 deque에 넣어서 찾아내는 방식으로 풀어야한다.
• 방문 처리를 통해서 queue에 리스트에 넣을지 넣지 않을지 체크한 후 방문하지 않았으면 queue에 현재 값과 값이 연산된 순서를 같이 넣어준 후 방문처리를 True 한다.
• BFS로 한 숫자에 대한 연산을 다 시행해가며 값을 찾아내고 종료시킨다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• BFS(너비 우선 탐색)