[백준] 14395번 : 4연산 - JAVA [자바]

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

bfs 알고리즘 문제이다.

1. 사전순에 맞게 각 연산을 하여 수를 만든다.
2. 이미 만들어진 수인지와 범위안에 들어가는 수인지 확인하여 큐에 삽입한다.
3. 목표 t가 되면 만든 연산을 출력한다.

visited 배열을 사용하면 범위가 커서 메모리 초과가 발생하므로 Set을 사용하여 만들어진 수인지 판별한다.

int 형을 사용하면 범위를 벗어나므로 long 형을 사용한다.

public class bj14395 {
    static long s, t, ANSWER = -1;
    static boolean yesAnswer = false;
    static String answer;
    static Set<Long> set = new HashSet<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String line = br.readLine();
        String[] split = line.split(" ");
        s = Integer.parseInt(split[0]);
        t = Integer.parseInt(split[1]);

        if (s == t) {
            System.out.println(0);
            System.exit(0);
        } else {
            bfs(new node(s, ""), new node(t, ""));

            if (!yesAnswer) {
                bw.write(ANSWER + "");
            } else {
                bw.write(answer);
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }

    public static void bfs(node s, node t) {
        Queue<node> queue = new LinkedList<>();
        queue.add(s);
        set.add(s.num);

        while (!queue.isEmpty()) {
            node current = queue.poll();

            if (current.num == t.num) {
                yesAnswer = true;
                answer = current.cul;
                break;
            }

            for (int i = 0; i < 4; i++) {
                if (i == 0) {
                    long newNum = current.num * current.num;
                    if (newNum < 1 || newNum > 1000000000) continue;
                    if (!set.contains(newNum)) {
                        set.add(newNum);
                        queue.add(new node(newNum, current.cul + "*"));
                    }
                } else if (i == 1) {
                    long newNum = current.num + current.num;
                    if (newNum < 1 || newNum > 1000000000) continue;
                    if (!set.contains(newNum)) {
                        set.add(newNum);
                        queue.add(new node(newNum, current.cul + "+"));
                    }
                } else if (i == 2) {
                    long newNum = current.num - current.num;
                    if (newNum < 1 || newNum > 1000000000) continue;
                    if (!set.contains(newNum)) {
                        set.add(newNum);
                        queue.add(new node(newNum, current.cul + "-"));
                    }
                } else {
                    if (current.num == 0) continue;
                    long newNum = current.num / current.num;
                    if (newNum < 1 || newNum > 1000000000) continue;
                    if (!set.contains(newNum)) {
                        set.add(newNum);
                        queue.add(new node(newNum, current.cul + "/"));
                    }
                }
            }
        }
    }

    public static class node {
        long num;
        String cul;

        public node(long num, String cul) {
            this.num = num;
            this.cul = cul;
        }
    }
}