문제 출처
https://www.acmicpc.net/problem/9019
9019번: DSLR
문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자) D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경
www.acmicpc.net
접근 방식 및 풀이
- BFS를 활용한다.
- 명령어를 한번씩 실행하면서 결과값을 저장하고, 계속 돌다가 출력해야하는 값이 나오면 종료하고 지금까지 실행한 명령어들을 출력한다.
- 소스코드는 백준 9019 DSLR Java 블로그를 참고하였다.
소스 코드
|
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
52
53
54
55
56
57
|
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i <n ; i++) {
int a = sc.nextInt();
int b =sc.nextInt();
String[] command = new String[10000]; // 정답 담는곳
boolean[] visited = new boolean[10000]; // BFS 탐색의 방문 여부 체크
Queue<Integer> q = new LinkedList<>();
visited[a] = true;
q.add(a);
Arrays.fill(command,"");
while (!q.isEmpty() && !visited[b]){
int now =q.poll();
int D = (2*now)%10000;
int S = (now == 0) ? 9999 : now-1;
int L = (now % 1000) * 10 + now/1000;
int R = (now % 10) * 1000 + now/10;
if(!visited[D]){
q.add(D);
visited[D]=true;
command[D]=command[now] + "D";
}
if(!visited[S]){
q.add(S);
visited[S]=true;
command[S]=command[now] + "S";
}
if(!visited[L]){
q.add(L);
visited[L]=true;
command[L]=command[now] + "L";
}
if(!visited[R]){
q.add(R);
visited[R]=true;
command[R]=command[now] + "R";
}
}
System.out.println(command[b]);
}
}
}
|
결과
'Competition > Baekjoon' 카테고리의 다른 글
| [백준][파이썬] 16236 아기상어 풀이코드 (0) | 2022.10.20 |
|---|---|
| [백준] 3108번 자바 로고 (0) | 2020.05.10 |
| [백준] 2632번 자바 피자 (0) | 2020.05.10 |