Life Engineering
[BOJ 9019] DSLR (Python3) 본문
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
44
45
46
47
48
49
50
51
|
from collections import deque
def D(n):
if n*2>9999:
return (n*2)%10000
return n*2
def S(n):
if n==0:
return 9999
return n-1
def L(n):
d1=n//1000
d2=(n%1000)//100
d3=((n%1000)%100)//10
d4=(((n%1000)%100)%10)
return ((d2*10+d3)*10+d4)*10+d1
def R(n):
d1=n//1000
d2=(n%1000)//100
d3=((n%1000)%100)//10
d4=(((n%1000)%100)%10)
return ((d4*10+d1)*10+d2)*10+d3
T=int(input())
array=[]
DSLR=["D","S","L","R"]
for _ in range(T):
array.append(list(map(int, input().split())))
def bfs(start, target):
queue=deque([start])
traces[start]="0"
while queue:
x=queue.popleft()
if x==target:
return traces[x][1:]
i=-1
for nx in (D(x), S(x), L(x), R(x)):
i+=1
if traces[nx]!="":
continue
traces[nx]=traces[x]+DSLR[i]
queue.append(nx)
for i in range(T):
traces=[""]*10000
print(bfs(array[i][0], array[i][1]))
|
cs |
BFS 문제이다. (BFS, DFS 문제만 푸는듯..딴 분야도 열심히 풀어야겠다)
스타트링크(BOJ 5014번)와 유사한 문제이다.
0부터 9999까지 숫자 배열을 만든 다음에 기록들을 저장한다.
각 점에서에서 D,S,L,R로 BFS 탐색 한 후, traces를 기록 후 큐에 넣어준다(이때 방문한 숫자는 탐색하지 않음).
queue에서 target 숫자가 나오면, traces[target]을 리턴한다. 이렇게 하면 최소한의 명령어 나열을 알 수 있다.
코드가 Little bit 더러운 느낌쓰.
다른 분들 코드 보니까 큐에 (DSLR 연산 한 숫자, way) 를 집어넣어 이 아이템을 pop 했을 때 해당 way에+수행한 연산을 덧붙이는 방식을 취했다. 이게 가독성이 더 좋고 간편한듯. 방문한 노드는 visited 배열을 통해 체크한다.
'Problem Solving' 카테고리의 다른 글
[BOJ 9465] 스티커 (Python3) (0) | 2021.02.22 |
---|---|
[BOJ 1912] 연속합 (Python3) (0) | 2021.02.22 |
[BOJ 9012] 괄호 (Python3) (0) | 2021.02.20 |
[BOJ 5014] 스타트링크 (Python3) (0) | 2021.02.20 |
[BOJ 2206] 벽 부수고 이동하기 (Python3) (0) | 2021.02.20 |