[BOJ 14395] 4연산 (Java, BFS)

---

문제 링크

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

14395번: 4연산

---

풀이

- BFS 그래프 탐색 문제 

- 첫 줄에 S, T 가 주어짐 (1 ≤ s, t ≤ 10^9)

- 현재 값과 연산자를 담은 Object를 정의해서 Queue에 담아 처리하도록함

 

에러

- 만약 배열 선언시 최대 10^9 까지 있기 때문에 '메모리 초과' 발생 

- 나누기(/) 연산시 값이 0 인 경우 '/ by zero' 에러 발생

 

실수 

- Set을 사용하여 이미 구한 값 여부 파악을 생각하지 못함

- 최대값이 10^9 이기 때문에 Integer로 할 경우 곱하기(*) 연산에서 범위 초과(overflow) 발생 가능 => 연산 값 Long으로 처리

---

제출 코드

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

public class Main {
    
    static long S, T;

   static void input() throws Exception {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       StringTokenizer st = new StringTokenizer(br.readLine());

       S = Integer.parseInt(st.nextToken());
       T = Integer.parseInt(st.nextToken());

       br.close();
   }

   static class Node {
       long value;
       String operator;

       public Node(long value, String operator) {
           this.value = value;
           this.operator = operator;
       }
   }

   static void func(long start) {
        String[] operators = new String[]{"*", "+", "-", "/"};

        Queue<Node> que = new LinkedList<>();
        que.add(new Node(start, ""));

        Set<Long> values = new HashSet<>();
        values.add(start);

        boolean find = false;
        while(!que.isEmpty()) {
            Node n = que.poll();
            if(n.value == T) {
                find = true;
                System.out.println(n.operator);
                break;
            }

            for(int i = 0; i < 4; i++) {
                String op = operators[i];
                if(n.value == 0 && op.equals("/")) continue; // / by zero

                long value = cal(n.value, op);
                if(!values.contains(value)) {
                    que.add(new Node(value, n.operator + op));
                    values.add(value);
                }
            }
        }

       if(!find) System.out.println(-1);
   }
    
   static long cal(long value, String op) {
       long result;
       if(op.equals("*")) {
           result = value * value;
       }else if(op.equals("+")) {
           result = value + value;
       }else if(op.equals("-")) {
           result = 0;
       } else { // 나누기
           result = 1;
       }

       return result;
   }

   static void pro() {
       if(S == T) System.out.println(0);
       else func(S);
   }

   public static void main(String[] args) throws Exception {
       input();
       pro();
   }
    
}