[백준 14395] 4연산 (Java)

문제 링크: www.acmicpc.net/problem/14395

14395번: 4연산

1. 주의할 점

- 출력에 있어 3가지의 경우가 있다

- 정답이 여러개인 경우, 사전순으로 앞선 경우를 출력한다

 

2. 구현

- BFS를 통해 정답을 도출한다

- 최대 범위가 10^9이므로 곱셈 혹은 덧셈의 결과가 10^9를 넘기지 않도록 한다

- 사전순으로 빠른 순서대로 BFS 탐색을 시작하며, 연산 결과의 숫자가 존재하지 않는 경우, Set과 큐에 추가한다

- 큐에서 꺼낸 원소가 Target과 같다면 Finish를 True로 전환 및 as에 cs를 할당하고 BFS를 종료한다

- Finish가 false면 -1을, true면 as의 값에 따라 답을 출력한다

 

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

public class Main {
    static HashSet<Integer> hs;
    
    static class Info {
        int val;
        String str="";
        public Info(int val, String str){
            this.val = val;
            this.str = str;
        }
    };
    
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    String ss = br.readLine();
        StringTokenizer st = new StringTokenizer(ss);
    	int start = Integer.parseInt(st.nextToken());
    	int target = Integer.parseInt(st.nextToken());
    	int mulMax = 34000, maxi=1000000000;
        //초기화
        hs = new HashSet<>();
        Queue<Info> q = new LinkedList<>();
        q.offer(new Info(start,""));
        String as="";
        boolean finish=false;
        
        while(!q.isEmpty()){
            Info ii = q.poll();
            int cv = ii.val;
            String cs = ii.str;
            if(cv==target){
                as = cs;
                finish=true;
                continue;
            }
            if(as.length()!=0 && as.length()<=cs.length()) continue;
            if(!hs.contains(0)){
                hs.add(0);
                q.offer(new Info(0,cs+"-"));
            }
            if(cv<=mulMax && !hs.contains(cv*cv)){
                q.offer(new Info(cv*cv,cs+"*"));
                hs.add(cv*cv);
            }
            if(cv+cv<=maxi && !hs.contains(cv+cv)){
                q.offer(new Info(cv+cv,cs+"+"));
                hs.add(cv+cv);
            }
            if(cv!=0 && !hs.contains(cv/cv)){
                q.offer(new Info(cv/cv,cs+"/"));
                hs.add(cv/cv);
            }
        }
        if(!finish) System.out.print(-1);
        else System.out.print(as.equals("")? 0 : as);
	}
}