[BaekJoon] 백준 9019번 : DSLR

9019번 : DSLR

[BaekJoon] 백준 1697번 : 숨바꼭질 이랑 비슷한 문제..

숨바꼭질 문제를 풀때는 미리 그래프를 다 그려 놓고 탐색을 했는데 이 문제를 풀면서 느꼈지만 그럴 필요가 없었다 !!

D, S, L, R 의 연산을 통해 나온 결과를 큐에 넣어가며 BFS 를 하면 된다..

그런데 처음에 L, R 연산을 잘못 이해하고 있어 엄청 애를 먹었다.

1 에다가 L 연산을 취하면 1이 되는게 아니라 10 이 되고

1 에다가 R 연산을 취하면 1이 되는게 아니라 1000 이 된다.

0001 이라고 생각하고 연산을 했어야 했다.. 그런줄도 모르고 단순히 그 숫자로만 하는 줄 알고 있었다.

L, R 연산은 조금 생각해보면 수식으로 만들 수 있다

만약 4758 을 L 연산 하고 싶다면 7580 + 4 로 만들면 되기 때문에 4758 % 1000 * 10 + 4758 % 1000 을 하면 된다.

이렇게 했는데 시간초과가 발생해 pypy3 으로 제출 해 통과했다.

---

import sys
from collections import deque


def find_min_route(a, b):

	visit = dict()
	start, end = a, b
	queue = deque([[start, '']])
	visit[start] = 1

	while queue:
		cur_node, cur_cal = queue.popleft()
		visit[cur_node] = 1
		D_i, S_i, L_i, R_i = D(cur_node), S(cur_node), L(cur_node), R(cur_node)

		if D_i not in visit:
			if D_i == end:
				return cur_cal + 'D'
			visit[D_i] = 1
			queue.append([D_i, cur_cal + 'D'])

		if S_i not in visit:
			if S_i == end:
				return cur_cal + 'S'
			visit[S_i] = 1
			queue.append([S_i, cur_cal + 'S'])

		if L_i not in visit:
			if L_i == end:
				return cur_cal + 'L'
			visit[L_i] = 1
			queue.append([L_i, cur_cal + 'L'])

		if R_i not in visit:
			if R_i == end:
				return cur_cal + 'R'
			visit[R_i] = 1
			queue.append([R_i, cur_cal + 'R'])


def D(a):
	return a * 2 % 10000


def S(a):
	return a - 1 if a != 0 else 9999


def L(a):
	return a % 1000 * 10 + a // 1000


def R(a):
	return a % 10 * 1000 + a // 10


for _ in range(int(input())):
	my_a, my_b = map(int, sys.stdin.readline().rsplit())
	print(find_min_route(my_a, my_b))