9019. DSLR (BFS)

사용한 알고리즘

BFS

 

 

접근했던 법

 

시작점에서 끝 점까지 가는 방법을 출력해야 한다. `True` 와 `False` 로 방문 여부만을 판단하는 일반적인 `visited`리스트를 사용하는 대신

1. visited = [''] * 10000 를 선언.
2. vstd에 '루트'들을 입력하며 방문처리와 루트 보관을 동시에 한다.
3. vstd[st] 에 아무 값(',')을 채워넣고 BFS 연산 시작.
4. vstd[ed] 가 None이 아닐 때 == 한 번이라도 닿았을 때
5. vstd[ed]를 출력하고 BFS 종료. 단, vstd[st]에서 임의의 값을 넣고 시작했으므로 적당한 슬라이싱이 필요.

어려웠던 점

'시작점에 방문 처리 안 해도 적당히 잘 풀리겠지' 하다가 틀렸다. 슬라이싱으로 오답을 받았다.

 

D, S, L, R을 최소한의 연산만으로 구해야 한다. ex) D = now *2 % 10000 if now * 2 > 10000 과 같은 비교문은 무의미함.

 

 

최적화

1. D, S, L, R을 구할 때 필요한 연산 횟수를 줄였다.

1번 코드는 2번 코드와 같은 일을 하면서 시행 시간은 더 짧다.

D = now*2 % 10000 
D = now*2 % 10000 if now*2 > 10000 else now*2

 

느낀 점

python3만으로 정답을 제출한 분들이 있다. 모듈을 더 공부해봐야겠다.

사소한 연산에서 풀이 시간을 줄여야 한다.

from collections import deque

def BFS(): # BFS 연산
    while Q:
        now = Q.popleft()

        if vstd[ed]: # 종료조건 - 도착점에 한 번이라도 방문했을 때
            print(vstd[ed][1:]) # 도착점으로 가는 path 인쇄
            return # 함수 즉시 종료.

        D = now*2 % 10000 # D.
        S = 9999 if not now else now - 1 # S.
        L = (now*10 + now//1000) % 10000 # L.
        R = now//10 + (now % 10) * 1000 # R.

        if not vstd[D]: # D에 방문하지 않았을 때
            Q.append(D) # Q에 D를 삽입하고
            vstd[D] = vstd[now] + 'D' # vstd[D] 에 지금까지의 루트 + 'D'

        if not vstd[S]:
            Q.append(S)
            vstd[S] = vstd[now] + 'S'

        if not vstd[L]:
            Q.append(L)
            vstd[L] = vstd[now] + 'L'

        if not vstd[R]:
            Q.append(R)
            vstd[R] = vstd[now] + 'R'


T = int(input()) # 테스트 케이스 입력 받음.

for times in range(T):
    st, ed = map(int, input().split()) # 시작, 끝
    Q = deque([st]) # 덱 선언 및 시작점 삽입.
    vstd = [''] * 10000 # 방문 여부 및 루트 기록용.
    vstd[st] = '.' # 시작점 표시.
    BFS()