정수 s가 주어진다. 정수 s의 값을 t로 바꾸는 최소 연산 횟수를 구하는 프로그램을 작성하시오.
사용할 수 있는 연산은 아래와 같다.
첫째 줄에 s와 t가 주어진다.
첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다.
연산의 아스키 코드 순서는 '*', '+', '-', '/' 이다.
7 392
+*+
7 256
/+***
4 256
**
7 7
0
7 9
-1
10 1
/
이 문제는 bfs(너비 우선 탐색) 알고리즘을 이용해서 쉽게 풀 수 있었다. 최대값이 이기 때문에 중복 체크를 HashSet을 이용했다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int start = Integer.parseInt(input[0]);
int target = Integer.parseInt(input[1]);
if(start==target) { //타겟 값과 같은 경우
System.out.println(0);
return;
}
bfs(start, target);
}
public static void bfs(int start, long target) {
Queue<Pair> queue = new LinkedList<>();
HashSet<Integer> set = new HashSet<>();
int min_len = Integer.MAX_VALUE;
String ans = "";
set.add(start);
queue.add(new Pair(start, ""));
while(!queue.isEmpty()) {
Pair temp = queue.poll();
if(temp.num==target) { //타겟 값에 도달한 경우 최소값 유효성 체크
if(min_len>=temp.str.length()) {
if(min_len==temp.str.length()) {
ans = ans.compareTo(temp.str) < 0 ? ans : temp.str;
}
else {
min_len = temp.str.length();
ans = temp.str;
}
}
}
if(!set.contains(0)) { //'-'는 무조건 0 이기 때문에 처음에 먼저 계산
set.add(0);
queue.add(new Pair(0, "-"));
}
if(!set.contains(1)) { //'/'는 무조건 1 이기 때문에 마찬가지로 먼저 계산
set.add(1);
queue.add(new Pair(1, "/"));
}
if((long)temp.num*temp.num<=target && !set.contains(temp.num*temp.num)) { //'*'가 가능한 경우, '*'가 '+'보다 아스키 코드 값이 작기 때문에 먼저 체크
if(temp.num*temp.num==target)
queue.add(new Pair(temp.num*temp.num, temp.str+"*"));
else {
set.add(temp.num*temp.num);
queue.add(new Pair(temp.num*temp.num, temp.str+"*"));
}
}
if((long)temp.num+temp.num<=target && !set.contains(temp.num+temp.num)) { //'+'가 가능한 경우
if(temp.num+temp.num==target)
queue.add(new Pair(temp.num+temp.num, temp.str+"+"));
else {
set.add(temp.num+temp.num);
queue.add(new Pair(temp.num+temp.num, temp.str+"+"));
}
}
}
if(ans.equals("")) //도달 불가능한 경우
System.out.println(-1);
else
System.out.println(ans);
}
public static class Pair {
int num;
String str;
public Pair(int num, String str) {
this.num = num;
this.str = str;
}
}
}