[백준]9019 DSLR

1. 풀이

일반적인 bfs를 사용하면 된다. 이때 주의할 점 세가지가 있다.

(1) 방문된것을 확인해주는 visited 리스트로 중복방문 관리하기.

-> visited로 중복방문을 관리해주지 않으면 방문한곳이 다시 방문되어 시간이 지수배로 증가한다.

(2) 문자열 처리보다 숫자처리가 훨씬 빠르다.

-> 몰랐어서 그냥 문자로 했다가 시간초과.

(3) python으론 안된다. pypy로 돌릴것.

​

2. 소스코드

(1) visited방문 처리x, 문자열로 순서처리, 시간초과

from collections import deque
import sys
d=["D","S","L","R"]

def do(num,order):
    if order=="D":
        return str((int(num)*2)%10000)
    elif order=="S":
        return str((int(num)-1)%10000)
    elif order=="L":
        tempL=list(num)
        tempL=num[1:]+num[0]
        return "".join(tempL)
    else:
        tempL=list(num)
        tempL=num[-1]+num[:-1]
        return "".join(tempL)

T=int(input())
for t in range(T):
    A,B=sys.stdin.readline().rstrip().split()
    q=deque([[A,""]])
    while(q):
        nowNum,sol=q.popleft()
        #print(nowNum)
        if int(nowNum)==int(B):
            print(sol)
            break
        for k in range(4):
            newNum=do(nowNum,d[k])
            q.append([newNum,sol+d[k]])

 

(2) 통과

from collections import deque
import sys
d=["D","S","L","R"]

def do(num,order):
    if order=="D":
        return (int(num)*2)%10000
    elif order=="S":
        return (int(num)-1)%10000
    elif order=="L":
        firstDigit = num // 1000
        return num % 1000 * 10 + firstDigit
    else:
        lastDigit = num % 10
        return num // 10 + 1000 * lastDigit

T=int(input())
for t in range(T):
    visited=[0 for i in range(10000)]
    A,B=map(int,sys.stdin.readline().rstrip().split())
    q=deque([[A,""]])
    visited[A]=1
    while(q):
        nowNum,sol=q.popleft()
        if nowNum==B:
            print(sol)
            break
        for k in range(4):
            newNum=do(nowNum,d[k])
            if not visited[newNum]:
                q.append([newNum,sol+d[k]])
                visited[newNum]=1