๐ ์ถ์ฒ - 9019 - DSLR
๋ฌธ์ ์ค๋ช
๋ค ๊ฐ์ ๋ช
๋ น์ด D, S, L, R ์ ์ด์ฉํ๋ ๊ฐ๋จํ ๊ณ์ฐ๊ธฐ๊ฐ ์๋ค. ์ด ๊ณ์ฐ๊ธฐ์๋ ๋ ์ง์คํฐ๊ฐ ํ๋ ์๋๋ฐ, ์ด ๋ ์ง์คํฐ์๋ 0 ์ด์ 10,000 ๋ฏธ๋ง์ ์ญ์ง์๋ฅผ ์ ์ฅํ ์ ์๋ค. ๊ฐ ๋ช
๋ น์ด๋ ์ด ๋ ์ง์คํฐ์ ์ ์ฅ๋ n์ ๋ค์๊ณผ ๊ฐ์ด ๋ณํํ๋ค. n์ ๋ค ์๋ฆฟ์๋ฅผ d1, d2, d3, d4๋ผ๊ณ ํ์(์ฆ n = ((d1 ร 10 + d2) ร 10 + d3) ร 10 + d4๋ผ๊ณ ํ์)
์์์ ์ธ๊ธํ ๊ฒ์ฒ๋ผ, L ๊ณผ R ๋ช ๋ น์ด๋ ์ญ์ง ์๋ฆฟ์๋ฅผ ๊ฐ์ ํ๊ณ ์ฐ์ฐ์ ์ํํ๋ค. ์๋ฅผ ๋ค์ด์ n = 1234 ๋ผ๋ฉด ์ฌ๊ธฐ์ L ์ ์ ์ฉํ๋ฉด 2341 ์ด ๋๊ณ R ์ ์ ์ฉํ๋ฉด 4123 ์ด ๋๋ค.
์ฌ๋ฌ๋ถ์ด ์์ฑํ ํ๋ก๊ทธ๋จ์ ์ฃผ์ด์ง ์๋ก ๋ค๋ฅธ ๋ ์ ์ A์ B(A โ B)์ ๋ํ์ฌ A๋ฅผ B๋ก ๋ฐ๊พธ๋ ์ต์ํ์ ๋ช ๋ น์ด๋ฅผ ์์ฑํ๋ ํ๋ก๊ทธ๋จ์ด๋ค. ์๋ฅผ ๋ค์ด์ A = 1234, B = 3412 ๋ผ๋ฉด ๋ค์๊ณผ ๊ฐ์ด ๋ ๊ฐ์ ๋ช ๋ น์ด๋ฅผ ์ ์ฉํ๋ฉด A๋ฅผ B๋ก ๋ณํํ ์ ์๋ค.
1234 โL 2341 โL 3412
1234 โR 4123 โR 3412
๋ฐ๋ผ์ ์ฌ๋ฌ๋ถ์ ํ๋ก๊ทธ๋จ์ ์ด ๊ฒฝ์ฐ์ LL ์ด๋ RR ์ ์ถ๋ ฅํด์ผ ํ๋ค.
n์ ์๋ฆฟ์๋ก 0 ์ด ํฌํจ๋ ๊ฒฝ์ฐ์ ์ฃผ์ํด์ผ ํ๋ค. ์๋ฅผ ๋ค์ด์ 1000 ์ L ์ ์ ์ฉํ๋ฉด 0001 ์ด ๋๋ฏ๋ก ๊ฒฐ๊ณผ๋ 1 ์ด ๋๋ค. ๊ทธ๋ฌ๋ R ์ ์ ์ฉํ๋ฉด 0100 ์ด ๋๋ฏ๋ก ๊ฒฐ๊ณผ๋ 100 ์ด ๋๋ค.
์
๋ ฅ
ํ๋ก๊ทธ๋จ ์
๋ ฅ์ T ๊ฐ์ ํ
์คํธ ์ผ์ด์ค๋ก ๊ตฌ์ฑ๋๋ค. ํ
์คํธ ์ผ์ด์ค ๊ฐ์ T ๋ ์
๋ ฅ์ ์ฒซ ์ค์ ์ฃผ์ด์ง๋ค. ๊ฐ ํ
์คํธ ์ผ์ด์ค๋ก๋ ๋ ๊ฐ์ ์ ์ A์ B(A โ B)๊ฐ ๊ณต๋ฐฑ์ผ๋ก ๋ถ๋ฆฌ๋์ด ์ฐจ๋ก๋ก ์ฃผ์ด์ง๋๋ฐ A๋ ๋ ์ง์คํฐ์ ์ด๊ธฐ ๊ฐ์ ๋ํ๋ด๊ณ B๋ ์ต์ข
๊ฐ์ ๋ํ๋ธ๋ค. A ์ B๋ ๋ชจ๋ 0 ์ด์ 10,000 ๋ฏธ๋ง์ด๋ค.
์ถ๋ ฅ
A์์ B๋ก ๋ณํํ๊ธฐ ์ํด ํ์ํ ์ต์ํ์ ๋ช
๋ น์ด ๋์ด์ ์ถ๋ ฅํ๋ค. ๊ฐ๋ฅํ ๋ช
๋ น์ด ๋์ด์ด ์ฌ๋ฌ๊ฐ์ง๋ฉด, ์๋ฌด๊ฑฐ๋ ์ถ๋ ฅํ๋ค.
์ ์ถ๋ ฅ ์
์์ ์ ๋ ฅ | ์์ ์ถ๋ ฅ |
---|---|
3 1234 3412 1000 1 1 16 | LL L DDDD |
๋ค์ ๋ก์ง์ BFS ์๊ณ ๋ฆฌ์ฆ์ ์ด์ฉํด ์ํํ๋ค ๊ฐ์ ๋ฐ๊ฒฌํ๋ฉด ์ถ๋ ฅํ๋ ๋ก์ง์ ๋๋ค.
Logic
BFS ์ค๋น๋ฌผ: deque, visited(๋ฐฉ๋ฌธ ํ์ธ)
1. ์ฒ์ ์ฃผ์ด์ง ์์ ๋น ๋ฌธ์์ด์ queue์ ๋ด์์ฃผ๋ฉด์ ์์ํ๋ค.
2. ๊ฐ๊ฐ D, S, L, R์ ๊ฒฝ์ฐ๋๋ก ์กฐ๊ฑด ์ค์
-D
๐* 2
ํ ๊ฐ์ ๊ฐ์ง๊ณ10000
์ผ๋ก ๋๋จธ์ง๋ฅผ ๊ตฌํด์ค (9999 ๋ณด๋ค ํฌ๋ฉด 10000์ผ๋ก ๋๋จธ์ง ย ย ย ย ย ย ย ย ย ย ย ๊ตฌํ๋ผ๋ ์กฐ๊ฑด์ด ์์๊ธฐ ๋๋ฌธ)
-S
๐-1
ํ ๊ฐ์ ๊ฐ์ง๊ณ10000
์ผ๋ก ๋๋จธ์ง๋ฅผ ๊ตฌํด์ค (n์ด 0์ด๋ผ๋ฉด 9999๊ฐ ์ ์ฅ๋์ผ ๋๋ค๋ ย ย ย ย ย ย ย ย ย ย ย ์กฐ๊ฑด์ด ์๊ธฐ ๋๋ฌธ =>-1 % 10000๋ฅผ ํ๊ฒ ๋๋ฉด 9999 ์ถ๋ ฅ
)
-L
๐ ๋งจ ์ผ์ชฝ์ ์๋ฅผ ๋งจ ์ค๋ฅธ์ชฝ์ผ๋ก ์ฎ๊ฒจ์ค์ผ ํ๊ธฐ ๋๋ฌธ์ ์๋์ ์ฝ๋์ ๊ฐ์ด ์์ฑ
ย ย ย ย ย ย ย ย ย ย ย(num % 1000) * 10 + num//1000)
-R
๐ ๋งจ ์ค๋ฅธ์ชฝ์ ์๋ฅผ ๋งจ ์ผ์ชฝ์ผ๋ก ์ฎ๊ฒจ์ค์ผ ํ๊ธฐ ๋๋ฌธ์ ์๋์ ์ฝ๋์ ๊ฐ์ด ์์ฑ
ย ย ย ย ย ย ย ย ย ย ย((num % 10) * 1000 + num//10)
3. ๊ฐ๊ฐDSLR
์ ์กฐ๊ฑด๋๋ก ํ์ ๋ ๋ฐฉ๋ฌธํ์ง ์์๋๋ผ๋ฉด, ๋ฐฉ๋ฌธ ์ฒดํน๊ณผ ๋์์queue
์
ย ย ย์ซ์์ ๊ฐ๊ฐ ํด๋น๋๋ ๋ฌธ์
์ฝ์
4.2, 3
์ ๋ฐ๋ณตํด์ค๊ณผ ๋์์ ์ํ๋ ์ซ์์ ์ผ์นํ๋ค๋ฉด ๊ทธ๋์ ๋ฌธ์์ด ์ถ๋ ฅ
from collections import deque
import sys
input = sys.stdin.readline
def bfs(before, after):
queue = deque()
queue.append((before, ""))
visited = [0] * 10000
visited[before] = 1
while queue:
num, word = queue.popleft()
if num == after:
return word
# D
if not visited[(num * 2) % 10000]:
queue.append(((num*2)%10000, word + "D"))
visited[(num * 2) % 10000] = 1
# S
if not visited[(num - 1) % 10000]:
queue.append(((num-1)%10000, word + "S"))
visited[(num - 1) % 10000] = 1
# L
if not visited[((num % 1000) * 10 + num//1000)]:
queue.append((((num % 1000) * 10 + num//1000), word + "L"))
visited[((num % 1000) * 10 + num//1000)] = 1
# R
if not visited[((num % 10) * 1000 + num//10)]:
queue.append((((num % 10) * 1000) + num // 10, word + "R"))
visited[((num % 10) * 1000) + num // 10] = 1
T = int(input())
for i in range(T):
before, after = map(int, input().split())
print(bfs(before, after))