[백준] 14395: 4연산 - JAVA

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

 

풀이

정수 s를 t로 바꾸는 최소 연산 횟수를 구한다.

연산은 `+, -, *, /` 를 사용할 수 있다.'

가능한 방법이 여러가지면 사전순으로 하나를 출력해야 하기 때문에 아스키 코드 순서인 `*, +, -, /` 순으로 탐색하였다.

s와 t가 10의 9제곱까지 주어지므로 최대 LIMIT을 1,000,000,000으로 잡았다.

탐색중에 이 범위를 넘지 않는 연산만 진행했다.

`/` 연산의 경우 숫자가 0이 아닐때만 사용가능하므로 처리해주었다.

bfs 탐색을 통해 가장 먼저 나오는 결과를 출력하면 끝.

 

---

 

메모리: 14424KB
시간: 132ms
언어: Java 11

import java.io.*;
import java.util.*;

public class Main {
    static final long LIMIT = 1_000_000_000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int s = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());

        if (s == t) {
            System.out.println(0);
        } else if (t == 1) {
            System.out.println("/");
        } else {
            System.out.println(bfs(s, t));
        }
    }

    private static String bfs(int s, int t) {
        Queue<Number> queue = new LinkedList<>();
        queue.add(new Number(s, ""));

        HashSet<Long> visited = new HashSet<>();

        while (!queue.isEmpty()) {
            Number node = queue.poll();
            if (node.num == t) {
                return node.history;
            }

            long now = node.num;

            if (now * now <= LIMIT && !visited.contains(now * now)) {
                visited.add(now * now);
                queue.add(new Number(now * now, node.history + "*"));
            }

            if (now + now <= LIMIT && !visited.contains(now + now)) {
                visited.add(now + now);
                queue.add(new Number(now + now, node.history + "+"));
            }

            if (now - now <= LIMIT && !visited.contains(now - now)) {
                visited.add(now - now);
                queue.add(new Number(now - now, node.history + "-"));
            }

            if (now > 0 && now / now <= LIMIT && !visited.contains(now / now)) {
                visited.add(now / now);
                queue.add(new Number(now / now, node.history + "/"));
            }
        }

        return "-1";
    }

    static class Number {
        long num;
        String history;

        public Number(long num, String history) {
            this.num = num;
            this.history = history;
        }
    }

}