알고리즘/백준
9019 DSLR
아메숑
2019. 3. 11. 08:14
1. 문제
2. 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | from collections import deque for t in range(int(input())): visit = [0]*100001 prev = [-1]*100001 A, B = map(int,input().split()) q = deque() q.append(A) visit[A] = 1 while q: nx= q.popleft() if nx == B: break D = (lambda x: 2*x%10000)(nx) S = 9999 if (nx ==0) else nx+1 kiri = len(str(nx)) - 1 #십집수의 길이 #print(kiri) L = (lambda x: x%(10**kiri)*10 + x//(10**kiri))(nx) R = (lambda x: x//10 + x%10*(10**kiri))(nx) cnt = -1 for i in [D,S,L,R]: cnt += 1 #i를 방문했어도 카운트 해야 하므로 방문체크 위에서 카운트를 한다. if visit[i] == 1: continue q.append(i) prev[i] = [nx,cnt] visit[i] = 1 path = [] p = ['D','S','L','R'] while prev[B] != -1: path.append(prev[B][1]) B = prev[B][0] for i in range(len(path)-1,-1,-1): print(p[path[i]], end='') print() | cs |
3. 후기
처음에는 bfs를 돌 때마다 경로를 스트링으로 저장했는데 시간초과가 나서 prev라는 리스트를 만들고 바로 전 경로를 저장했다. 근데 그래도 시간초과가 난다. 파이썬으로 작성한 코드는 맞았습니다가 없었다. 다음부터는 c++로 해야겠다.