[BaekJoon] 14395 4연산 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/14395

2.  문제

요약

• 정수 s가 주어지면, 정수 s의 값을 t로 바꾸는 최소 연산 횟수를 구하는 문제입니다.
• 사용할 수 있는 연산은 아래와 같습니다.
  1. s = s + s;
  2. s = s - s;
  3. s = s * s;
  4. s = s / s; (s가 0이 아닐 때만 사용 가능합니다)
• 입력: 첫 번째 줄에 1보다 크거나 같고 $10^9$보다 작거나 같은 s와 t가 주어집니다.
• 출력: 첫 번째 줄에 정수 s를 t로 바꾸는 방법을 출력합니다.
  • s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력합니다.
  • 가능한 방법이 여러가지라면 사전 순으로 앞서는 것을 출력합니다.
    • 연산의 아스키 코드 순서는 '*', '+', '-', '/' 입니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static long s, t;
	static String[] operator = {"*", "+"};
	public long calculate(long num, int operator_index) {
		if(operator_index == 0) {
			if(num * num > t || num == 1) {
				return - 1;
			}
			return num * num;
		} else {
			if(num + num > t || num == 2) {
				return - 1;
			}
			return num + num;
		}
	}
	
	public String getOperandSet() {
		Queue<Number> queue = new LinkedList<Number>();
		queue.offer(new Number(s * s, "*"));
		queue.offer(new Number(s + s, "+"));
		queue.offer(new Number(1, "/"));
		HashSet<Long> set = new HashSet<Long>();
		while(!queue.isEmpty()) {
			Number cur_num = queue.poll();
			if(cur_num.num == t) {
				return cur_num.expression;
			}
			if(cur_num.num > t) {
				continue;
			}
			for(int i = 0; i < 2; i++) {
				long next_num = calculate(cur_num.num, i);
				if(next_num == -1 || set.contains(next_num)) {
					continue;
				}
				set.add(next_num);
				queue.offer(new Number(next_num, cur_num.expression + operator[i]));
			}
		}
		return "-1";
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		br.close();
		s = Long.parseLong(input[0]);
		t = Long.parseLong(input[1]);
		Main m = new Main();
		if(s == t)
			bw.write(0 + "\n");
		else if(t == 1)
			bw.write("/" + "\n");
		else if(t == 0)
			bw.write("-" + "\n");
		else {
			bw.write(m.getOperandSet() + "\n");
		}
		bw.flush();
		bw.close();
	}
	
	public static class Number {
		long num;
		String expression = "";
		public Number(long num, String expression) {
			this.num = num;
			this.expression = expression;
		}
	}
}

4.  접근

• 해당 문제는 BFS를 이용하여 해결할 수 있습니다.
• 만약 t가 1이라면, 나누기를 통해 바로 1을 만들 수 있으므로 /를 출력합니다.
• 만약 t가 0이라면, 빼기를 통해 바로 0을 만들 수 있으므로 -를 출력합니다.
• 위에서 얘기한 바와 같이, 나누기와 빼기는 연산을 진행한다면 무조건 각각 1과 0이 나오기 때문에 처음 연산 시에 나누기를 제외하고는 t를 만들기 위해 연산을 진행할 때 고려사항에서 제외시킬 수 있습니다.
• 그렇기 때문에 BFS를 처음 진행할 때, Queue에 주어진 s에 대해 연산의 사전 순서대로 곱하기, 더하기, 나누기 연산을 진행한 값들을 각각 넣어준 후에 BFS를 진행합니다.
• Queue에서 탐색을 진행할 수를 꺼낸 뒤에 해당 수에 대해 연산의 사전 순서대로 곱하기 연산과 더하기 연산을 각각 진행합니다.
• 이 때, 만약 곱하기 연산을 진행하는데 진행하려는 값이 1이라면, 계속해서 1이 나오기 때문에 해당 연산에 대해서는 더 이상 진행하지 않고 연산을 진행했는데 값이 t보다 크다면, 연산을 진행할 때 고려하는 사항이 곱셈과 덧셈 밖에 없기 때문에 계속해서 값이 커지는 연산이므로 t가 될 수 없기 때문에 해당 연산에 대해서는 더 이상 진행하지 않습니다.
• 또한, 만약 더하기 연산을 진행하는데 진행하려는 값이 2라면, 이미 곱하기에서 진행한 연산이기 때문에 해당 연산은 더 이상 진행하지 않고, 만약 연산을 진행했는데 해당 값이 t보다 크다면 곱하기에서와 같은 이유로 해당 연산에 대해서는 더 이상 진행하지 않습니다.
• 이렇게 두 연산을 진행해가면서 Queue에 연산된 값들을 집어넣고 HashSet을 하나 생성하여 HashSet에도 연산된 값을 넣습니다.
• 연산을 진행하는데 만약 위의 이유로 더 이상 진행하지 않는 연산이거나 연산된 값이 HashSet에 있는 값이라면 해당 값에 대해서는 더 이상 연산을 진행하지 않습니다.
  • HashSet에 있다는 것은 이전에 이미 만들어졌던 값이라는 뜻이므로 그렇다면 해당 값은 연산을 진행해봤자 이후에 다시 해당 값이 나올 것이기 때문에 해당 값에 대해서는 더 이상 연산을 진행하지 않습니다.
• 위 방법들을 토대로 정수 s를 t로 바꾸는 방법을 출력합니다.