[Algo] 백준 14395 4연산 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/14395

메모리 : 14520 KB

시간 : 132ms

언어 : Java 11

---

코드

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

class Main {
    static class Node {
        long num;
        String str;

        Node(long num, String str) {
            this.num = num;
            this.str = str;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long s = Integer.parseInt(st.nextToken());
        long t = Integer.parseInt(st.nextToken());
        if (s == t) {
            System.out.println(0);
            return;
        }
        HashSet<Long> check = new HashSet<>();
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(s, ""));
        check.add(s);
        while (!q.isEmpty()) {
            Node n = q.poll();
            if (n.num == t) {
                System.out.println(n.str);
                return;
            }
            if (n.num * n.num <= t && !check.contains(n.num * n.num)) {
                check.add(n.num * n.num);
                q.add(new Node(n.num * n.num, n.str + "*"));
            }
            if (n.num + n.num <= t && !check.contains(n.num + n.num)) {
                check.add(n.num + n.num);
                q.add(new Node(n.num + n.num, n.str + "+"));
            }
            if (n.num - n.num <= t && !check.contains(n.num - n.num)) {
                check.add(n.num - n.num);
                q.add(new Node(n.num - n.num, n.str + "-"));
            }
            if (0 != n.num && n.num / n.num <= t && !check.contains(n.num / n.num)) {
                check.add(n.num / n.num);
                q.add(new Node(n.num / n.num, n.str + "/"));
            }
        }
        System.out.println(-1);
    }
}

 

풀이

간단한 bfs문제이다. * + - / 순서로 탐색을 돌면 된다. 한 가지 특이한 점은 bfs해오던 방문체크를 배열로 하지 않았다는 점이다. 배열로 방문체크를 하게되면 int범위가 넘어가는 수에 대해서 ArrayIndexOutOfBoundsException가 발생하기 때문이다. 때문에 set에 숫자를 장해 contains로 확인하는 방법을 사용했다.