[Java] 백준(골드-4) 9019번 - DSLR
문제 풀이
이번 문제는 너비 우선 탐색 BFS을 응용하여 풀 수 있는 문제이다.
아이디어 도출
여태 BFS를 이용하며, 지도 배열에서 상,하,좌,우를 탐색할 dx, dy 배열을 이용했지만, 이번 문제는 D,S,L,R이라는 특수 명령마다 탐색해가며 누적되는 문자열을 반환해야 하는 문제이기에 별도의 레지스터 값과 문자열을 담을 클래스를 이용하게 되었다.
그렇게, A라는 수를 B로 표현할 수 있는 최소한의 방법인 수행할 명령을 나열한 문자열을 출력하는 방법을 살펴보자.
- BFS를 통해 A라는 수를 D,S,L,R 명령을 통해 변환한다.
- 문제의 요구사항을 잘 살펴서 D, S, L, R 명령을 수행한다.(자세한 내용은 아래에서 확인!)
- D,S,L,R 명령을 수행하며 변환된 레지스터 값이 B가 된다면 탐색을 종료한다.
- 변환 과정에서 수행한 명령을 문자열로 출력하면 된다.
D,S,L,R 명령 수행
- D: 수를 2배로 바꾸고 10000으로 나눈 나머지로 갱신한다.
- S: 수를 0일 때, 9999, 아니면 1을 빼준다
- L: 왼쪽으로 자리수를 바꾼다.
1234 -> 2341, 1234를 1000으로 나눈 나머지(234)에 10을 곱함=2340, 1234를 1000으로 나누면 1, 2340+1=2341- R: 오른쪽으로 자리수를 바꾼다.
1234 -> 4123, 1234를 10으로 나눈 나머지에 1000 곱합 = 4000, 1234를 10으로 나누면 123, 4000+123=4123
이때, 현재까지의 레지스터값과 수행한 명령어를 담을 Register라는 클래스를 사용하였다.
그렇게 모든 경우에서 4가지 명령어를 실행하고 각각의 실행한 경우에서 또 명령어를 실행하도록 반복하였고 결국, 변환된 값이 B가 되었을때 누적된 문자열(명령어)를 반환하도록 구현했다.
문제 풀이를 위해 작성한 코드는 아래와 같다.
작성코드
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
import java.io.*;
import java.util.*;
class Main {
// 방문 배열 선언
static boolean[] visited;
// D,S,L,R 명령을 담을 배열 선언
static char[] cmds = new char[]{'D', 'S', 'L', 'R'};
public static void main(String[] args) throws IOException {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
int T = Integer.parseInt(br.readLine());
while(T --> 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
visited = new boolean[10000];
String result = bfs(A, B);
bw.write(result+"\n");
}
}
}
// D,S,L,R 만큼 너비우번 탐색을 진행할 bfs 함수
public static String bfs(int start, int end) {
Queue<Register> q = new LinkedList<>();
q.offer(new Register(start, ""));
visited[start] = true;
while(!q.isEmpty()) {
Register now = q.poll();
// 만약 A와 B가 같다면 변환이 성공한 것이니 탐색을 종료한다.
if(now.num == end) {
return now.command;
}
// D,S,L,R 4번을 반복한다.
for(int i=0; i<4; i++) {
int change = changeRegister(now.num, cmds[i]);
if(!visited[change]) {
visited[change] = true;
q.offer(new Register(change, now.command + cmds[i]));
}
}
}
return "";
}
/**
* D,S,L,R 명령별 기능을 수행할 함수
* D: 수를 2배로 바꾸고 10000으로 나눈 나머지로 갱신한다.
* S: 수를 0일 때, 9999, 아니면 1을 빼준다
* L: 왼쪽으로 자리수를 바꾼다.
* R: 오른쪽으로 자리수를 바꾼다.
*/
public static int changeRegister(int num, char cmd) {
switch(cmd) {
case 'D':
num *= 2;
if(num > 9999) {
num %= 10000;
}
break;
case 'S':
num -= 1;
if(num == -1) {
num = 9999;
}
break;
case 'L':
int tmp_l1 = (num % 1000) * 10;
int tmp_l2 = num / 1000;
num = tmp_l1 + tmp_l2;
break;
case 'R':
int tmp_r1 = num / 10;
int tmp_r2 = (num % 10) * 1000;
num = tmp_r1 + tmp_r2;
break;
default:
break;
}
return num;
}
// register값과 수행한 명령을 담을 Register 클래스
public static class Register {
int num;
String command;
public Register(int num, String command) {
this.num = num;
this.command = command;
}
}
}
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.