[BOJ] 9019. DSLR(Python) / BFS

www.acmicpc.net/problem/9019

9019번: DSLR

처음에는 DFS로 접근했다가 그렇게 해서는 답도 없을 것 같아서 BFS를 떠올렸는데, 결국 혼자 힘으로 못 풀고 다른 사람의 풀이를 봤다ㅠㅠ

• 사용 알고리즘 : BFS(최단거리 알고리즘)
• 여러 설명보다 아래 코드를 보면 이해할 수 있을 것이다.
• 4자리 숫자이므로 일차원 배열 visited를 10000 크기로 만든다.
• while문을 돌 때마다 현재 temp에
  • D, S, L, R 연산을 해주며 큐에 (연산한 현재 값, 어떤 연산인지) 정보를 더하면서 담는다.
  • 방문하지 않았을 경우에 방문처리를 한다.
• 큐에서 값을 꺼낼 때 목표 숫자라면 그 떄의 연산 정보를 즉시 리턴한다.

 

파이썬 코드는 다음과 같다.

---

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

def bfs(start, end):
    Q = deque([(start, '')])
    visited = [0] * 10000
    visited[start] = 1
    while Q:
        num, temp = Q.popleft()

        if num == end:       # 목표 숫자에 도달하면 리턴
            return temp
        # D
        if not visited[num*2 % 10000]:
            visited[num*2 % 10000] = 1
            Q.append((num*2 % 10000, temp+"D"))
        # S
        if not visited[(num-1) % 10000]:
            visited[(num-1) % 10000] = 1
            Q.append(((num-1) % 10000, temp+"S"))
        # L
        if not visited[num % 1000 * 10 + num//1000]:
            visited[num % 1000*10 + num//1000] = 1
            Q.append((num % 1000*10 + num//1000, temp+"L"))
        # R
        if not visited[num % 10*1000 + num//10]:
            visited[num % 10*1000 + num//10] = 1
            Q.append((num % 10*1000 + num//10, temp+"R"))

# main
T = int(input())
for _ in range(T):
    A, B = map(int, input().split())
    print(bfs(A, B))

---

• 시간 : 4404ms / 메모리 : 226720kb
• 고찰 : 나는 다른 사람의 풀이를 보고 풀어서 괜찮았지만, 시간 초과가 많이 나는 문제라고 한다. 어떤 단어까지 빨리 도달하는 문제는 BFS로 접근하자. 처음 문제를 보고 어렵다 생각해서 겁을 먹은 것 같다,, 조금만 생각하면 생각보다 쉽게 풀릴 수 있는 문제들이 많다! 이 문제 역시 풀이를 알고보니 충분히 혼자 힘으로 풀 수 있는 문제였을 것 같다.