백준 16953번 : A → B
이번 문제는 정수 A와 B를 입력 받았을 때, A를 B로 변경하는데 필요한 연상의 최솟값을 구하는 문제이다.
여기서 A가 B로 변경될 때 가능한 연산은 두 가지이다.
- 2를 곱한다.
- 1을 수의 가장 오른쪽에 추가한다.
위의 두 가지 연산 과정을 거쳐 최소 연산 후 1을 더한 값을 출력해야한다.
단, 만들 수 없는 경우 -1을 출력한다.
a,b를 입력받고서 큐를 생성하고 BFS 탐색을 시작하면 되는데, 시작 전에 해당 큐에 a와 연산 횟수를 담은 배열을 삽입하고 시작한다.
1
2
Queue<long[]> q = new LinkedList<>();
q.add(new long[]{a, 1});
여기서 a의 값은 최대 10^9 - 1까지이기 때문에 long 타입으로 초기화 했고, 배열의 두 번째 값인 count(연산 횟수)는 int 형으로 초기화해도 괜찮지만 Object 배열을 사용해서 다운캐스팅 하는 것보다 long 타입 배열에 같이 초기화하는게 불필요한 연산을 줄일 수 있을 것이라 생각해 long 타입으로 통일했다.
이제 BFS 탐색을 시작해야한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
while (!q.isEmpty()) {
long[] cur = q.poll();
long value = cur[0];
long count = cur[1];
if (value == b) {
System.out.println(count);
return;
}
if (value * 2 <= b) {
q.add(new long[]{value * 2, count + 1});
}
if (value * 10 + 1 <= b) {
q.add(new long[]{value * 10 + 1, count + 1});
}
}
결국 최소 연산 횟수를 구하는 문제이기 때문에 BFS 탐색을 선택했고, q가 빌 때까지 반복을 실행한다.
다만 인접 행렬을 탐색하는 문제는 아니기 때문에 이전과 같이 방향을 지정하고, 해당 방향을 탐색하는 방식은 사용하지 않는다.
큐에 담긴 값을 추출해 각각 value와 count 변수에 할당한 다음 조건을 분기하여 값을 추가하거나 B에 도달하면 리턴한다.
우선 가장 처음 구현된 조건문은 A가 B에 도달한 경우 count(연산 횟수)를 출력하고 종료하는 조건이다.
그 다음 두 개의 조건은 각각 문제에서 제시한 연산 과정이다.
1. 2를 곱한다.
1
2
3
if (value * 2 <= b) {
q.add(new long[]{value * 2, count + 1});
}
먼저 A에 2를 곱한 다음, 이 값이 B보다 작거나 같은 경우 q에 해당 결과를 value로 삽입하고 연산 과정 횟수를 한 번 추가한다.
2. 1을 수의 가장 오른쪽에 추가한다.
1
2
3
if (value * 10 + 1 <= b) {
q.add(new long[]{value * 10 + 1, count + 1});
}
다음으로는 A의 가장 우측에 1을 추가한다.
10을 곱한다음 1을 추가하면 해당 연산이 된다.
마찬가지로 B보다 작거나 같은 경우 해당 연산 결과를 value로, 횟수를 한 번 늘린다.
이 조건은 else가 아니라 두 개 다 실행되기 때문에 그때그때 최적의 해를 구한다기 보다는 모든 해를 탐색하는 방식이다.
예를 들어, A = 2 / B = 162가 입력되었을 때의 흐름은 다음과 같다.
- 초기 값 2와 연산 횟수 1을 큐에 넣는다. (큐 : {2, 1})
- 큐에서 값을 꺼낸다. 현재 값은 2, 연산 횟수는 1이다.
- 2 * 2 = 4가 162 이하이므로, 큐에 {4, 2}를 넣는다. (큐 : {4, 2})
- 2 * 10 + 1 = 21이 162 이하이므로, 큐에 {21, 2}를 넣는다. (큐 : {4, 2}, {21, 2})
- 큐에서 값을 꺼낸다. 현재 값은 4, 연산 횟수는 2이다.
- 4 * 2 = 8이 162 이하이므로, 큐에 {8, 3}를 넣는다. (큐 : {21, 2}, {8, 3})
- 4 * 10 + 1 = 41이 162 이하이므로, 큐에 {41, 3}를 넣는다. (큐 : {21, 2}, {8, 3}, {41, 3})
- 큐에서 값을 꺼낸다. 현재 값은 21, 연산 횟수는 2이다.
- 21 * 2 = 42이 162 이하이므로, 큐에 {42, 3}를 넣는다. (큐 : {8, 3}, {41, 3}, {42, 3})
- 21 * 10 + 1 = 211이 162 초과이므로, 이 연산은 수행하지 않는다.
- 큐에서 값을 꺼낸다. 현재 값은 8, 연산 횟수는 3입니다.
- 8 * 2 = 16이 162 이하이므로, 큐에 {16, 4}를 넣는다. (큐 : {41, 3}, {42, 3}, {16, 4})
- 8 * 10 + 1 = 81이 162 이하이므로, 큐에 {81, 4}를 넣는다. (큐 : {41, 3}, {42, 3}, {16, 4}, {81, 4})
- 이 과정을 계속 반복하면, {162, 5}를 얻을 수 있다. 따라서, 2를 162로 만드는 최소 연산 횟수는 5번이다.
연산 과정을 거쳐 마지막에 B에 도달한다면 첫 조건문에서 걸리기 때문에 count를 리턴하면 연산 횟수가 되고, 만약 연산과정을 거쳐 b보다 커지게되면 큐에 값이 담기지 않기 때문에 while 반복문이 종료되고 도달할 수 없는 경우이기 때문에 -1를 출력한다.
문제의 힌트에서는 그리디 알고리즘이라고 소개되어 있지만 내 풀이는 최적의 해를 결정하는 로직이 없기 때문에 단순한 BFS 알고리즘이라고 볼 수 있다.
전체 소스코드는 다음과 같다.
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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
long a = Integer.parseInt(st.nextToken());
long b = Integer.parseInt(st.nextToken());
Queue<long[]> q = new LinkedList<>();
q.add(new long[]{a, 1});
while (!q.isEmpty()) {
long[] cur = q.poll();
long value = cur[0];
long count = cur[1];
if (value == b) {
System.out.println(count);
return;
}
if (value * 2 <= b) {
q.add(new long[]{value * 2, count + 1});
}
if (value * 10 + 1 <= b) {
q.add(new long[]{value * 10 + 1, count + 1});
}
}
System.out.println(-1);
}
}
문제의 난이도 자체는 어렵지 않지만 조건을 분기하는데 조금 헷갈릴 수 있다.
이후 이런 문제가 나올 때 빠르게 파악하기 위해 기록한다.