[JAVA] 백준 - 4연산 14395( BFS)

www.acmicpc.net/problem/14395

14395번: 4연산

 

처음 숫자가 s 라고 할때

 

다음 숫자는 = s + s || s - s || s * s ||  s /  s 이다.

 

'-' 와 '/' 는 반드시 0 과 1 이된다. 

 

사실 t 가 0 이면  '-' 를 반환하면 되고

t가 1이면 '/'를 반환하면 된다.

 

그렇다고 해서 '/' 와 '-' 를 연산에서 제거하면 안된다. 모든 경우의 수를 살펴야 한다. 예를 들어

 

s = 10 / t = 8 이라면

 

(((10 / 10) + 1 )* 2) + 4 로 답은 '/+*+' 이다.

 

즉, '-' 와 '/' 다음에도 연산이 올 수 있다. 이것과 0으로 나누는 것만 조심해서 BFS 로직에 녹여주면 된다.

 

# 자바 코드

 

long 을 사용하긴 했는데 이는 10^9 을 넘어가는 것을 체크하기 위해 사용했지만 int 가 21억까지 커버되므로 long을 안해도 된다.

 

또한 String 컬렉션을 정렬하면 자동으로 사전순으로 정렬해준다.

 

import java.util.LinkedList;
import java.util.*;

class Main{
    static long s,t;
    static HashSet<Long> set = new HashSet<>();
    static ArrayList<String> ansList = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        s = sc.nextLong();
        t = sc.nextLong();

        if(s==t) {
            System.out.println(0);
            return;
        }

        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(s));
        set.add(s);

        while(!q.isEmpty()){
            Pair p = q.poll();

            if(p.num == t){
                String temp = "";
                for(int i=0;i<p.ops.size();i++) temp+=p.ops.get(i);
                ansList.add(temp);
            }

            long next = p.num * p.num;
            if(next <= Math.pow(10,9) && !set.contains(next)){
                set.add(next);
                Pair tp = new Pair(next);
                for(int i=0;i<p.ops.size();i++) tp.ops.add(p.ops.get(i));
                tp.ops.add('*');
                q.add(tp);
            }

            next = 0L;
            if(!set.contains(next)){
                set.add(0L);
                Pair tp = new Pair(next);
                for(int i=0;i<p.ops.size();i++) tp.ops.add(p.ops.get(i));
                tp.ops.add('-');
                q.add(tp);
            }

            next = p.num + p.num;
            if(next <= Math.pow(10,9) && !set.contains(next)){
                set.add(next);
                Pair tp = new Pair(next);
                for(int i=0;i<p.ops.size();i++) tp.ops.add(p.ops.get(i));
                tp.ops.add('+');
                q.add(tp);
            }
            if(p.num != 0){
                next = 1L;
                if(!set.contains(next)){
                    set.add(next);
                    Pair tp = new Pair(next);
                    for(int i=0;i<p.ops.size();i++) tp.ops.add(p.ops.get(i));
                    tp.ops.add('/');
                    q.add(tp);
                }
            }
        }


        Collections.sort(ansList);
        System.out.println(ansList.size()==0?-1:ansList.get(0));



    }


    static class Pair{
        long num;
        ArrayList<Character> ops = new ArrayList<>();

        public Pair(long num){
            this.num = num;
        }
    }
}