백준 14395번 4연산(JAVA)

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

14395번: 4연산

 

저는 구현을 통해 문제를 해결하였습니다.

방문체크는 그 숫자로 하였고, /는 0일때 하면 안되기 때문에 지금 숫자가 0이라면 continue를 통해 안하게 구현하였습니다.

시작 숫자와 끝 숫자가 같다면 처음부터 0을 리턴하도록하고 못구한다면 -1을 리턴하였습니다.

package BOJ.bfs;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_14395 {
    private static class Node{
        long num;
        String operations;

        public Node(long num, String operations) {
            this.num = num;
            this.operations = operations;
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Function<String,Integer> stoi = Integer::parseInt;
        int startNum = stoi.apply(st.nextToken());
        int endNum = stoi.apply(st.nextToken());
        String result = bfs(startNum,endNum);
        System.out.println(result);
    }
    private static char[] OPERATION = {'*','+','-','/'};
    private static String bfs(int startNum, int endNum) {
        if(startNum == endNum){
            return "0";
        }
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(startNum,"") );
        Set<Long> visited = new HashSet<>();
        while(!q.isEmpty()){
            Node now = q.poll();
            if(now.num == endNum){
                return now.operations;
            }
            long nextNum = now.num * now.num;
            if(!visited.contains(nextNum)){
                visited.add(nextNum);
                q.offer(new Node(nextNum,now.operations+"*"));
            }
            nextNum = now.num + now.num;
            if(!visited.contains(nextNum)){
                visited.add(nextNum);
                q.offer(new Node(nextNum,now.operations+"+"));
            }
            nextNum = now.num - now.num;
            if(!visited.contains(nextNum)){
                visited.add(nextNum);
                q.offer(new Node(nextNum,now.operations+"-"));
            }
            if(now.num == 0){
                continue;
            }
            nextNum = now.num / now.num;
            if(!visited.contains(nextNum)){
                visited.add(nextNum);
                q.offer(new Node(nextNum,now.operations+"/"));
            }
        }
        return "-1";
    }
}