[백준] 14395번 4연산 Java

문제 링크

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

알고리즘: BFS

문제

정수 s가 주어진다. 정수 s의 값을 t로 바꾸는 최소 연산 횟수를 구하는 프로그램을 작성하시오.

사용할 수 있는 연산은 아래와 같다.

1. s = s + s; (출력: +)
2. s = s - s; (출력: -)
3. s = s s; (출력: )
4. s = s / s; (출력: /) (s가 0이 아닐때만 사용 가능)

풀이

중복 체크는 HashMap을 이용했다.
현재 s 값에 4가지 연산을 중복 없이 범위에 벗어나지 않는다면 Queue에 넣어주고 T 값이 된다면 return 해주면 된다.
단 최소 연산 횟수가 같은 경우는 사전 순으로 앞서는 것을 출력하기 위해서
(연산의 아스키코드 순서는 '', '+', '-', '/')
Queue에 -> + -> - -> /순으로 넣어준다.
Queue에 특성상 선입 선출이기 때문에 같은 횟수가 여러 개라도 사전 순으로 앞선 값이 먼저 return 조건에 들어오기 때문이다.

소스 코드

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

class Node {
    long s;
    String op;
    Node(long s, String op) {
        this.s = s;
        this.op = op;
    }
}

public class Main {
    static final char op_arr[] = {'*','+','/'};
    static final long MAX_RANGE = 1000000000;
    static Node start;
    static String ans;
    static long S,T;
    static Map<Long, Boolean> map_visited = new HashMap<Long, Boolean>();
    public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      S = Integer.parseInt(st.nextToken());
      T = Integer.parseInt(st.nextToken());
      start = new Node(S, "");
      if(S==T) {
          System.out.println(0);
      } else {
          BFS();
          if(ans == null) {
              System.out.println(-1);
          } else {
              System.out.println(ans);
          }
      }
    }
    
    static void BFS() {
        Queue<Node> que = new LinkedList<>();
        que.add(start);
        map_visited.put(start.s, true);
        while(!que.isEmpty()) {
            Node n = que.poll();
            if(n.s == T) {
                ans = n.op;
                return;
            }
            for(int i=0; i<op_arr.length; i++) {
                long ns = calculate(n.s, op_arr[i]);
                if(ns>=1 && ns <= MAX_RANGE) {
                    if(map_visited.get(ns) == null) {
                        map_visited.put(ns, true);
                        que.add(new Node(ns, n.op+op_arr[i]));
                    }
                }
            }
        }
        return;
    }
    static long calculate(long v, char op) {
        if(op == '*') {
            return v*v;
        } else if(op == '+') {
            return v+v;
        } else {
            return v/v;
        }
    }
    
}