[백준] 14395 4연산 - BFS + HashSet + 자료형 범위 JAVA

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

14395번: 4연산

코드설명

BFS 문제에 자료형 범위를 고려해야합니다.

 

항상 이러한 문제를 보면 DFS로 풀지, BFS로 풀지 고민이 됩니다.  

이 문제는 BFS로 접근하는데는 성공하였지만, 명확한 근거를 가지고서 어떤 알고리즘을 사용할지 생각이 필요합니다.

일차적으로 BFS와 DFS 둘다 사용가능할지 생각하는 과정이 꼭 필요한 것 같습니다.

 

처음에 풀었을때는 t

첫째 줄에 s와 t가 주어진다. (1 ≤ s, t ≤ 10^9)

처음에 10^9 을 보고, 10억의 범위이니 굳이 Integer를 써야겠다라고 생각했습니다.

그래서 visited[10^9]을 선언하고, 진행하였고, 그 과정에서 Overflow가 날 가능성은

s = s * s 를 할 경우이기에 Math.sqrt(10^9) 의 값 이내에 있을때만 가능하도록 설정하였지만 계속해서 Array OutofBound가 나왔습니다.

 

그렇기에 long 형으로 선언하고, visited[] 배열 대신 HashSet을 활용하여 중복처리를 진행했습니다.

이 과정에서 아래와 같이 일종의 범위를 다스리며 진행하려고하였지만, 그렇게 할경우 최소경로를 구하는 방식을 해치는 것 같습니다. 그렇기에 조건을 해제하고 진행하면 됩니다.

next >= 1 && next <= MAX

 

이 문제에서 처음에는 DFS를 통해 진행하려고하였지만, 최소연산횟수를 구하는것이므로 BFS를 사용하면 쉽게 해결할 수 있습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	public static long s, t;
	public static long MAX = 100000000;
	public static String answer="";
	public static HashSet<Long> hashset = new HashSet<>();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	s = Long.parseLong(st.nextToken());
    	t = Long.parseLong(st.nextToken());
    	if(s == t) {
    		System.out.println(0);
    		return ;
    	}
    	simulate(new Node(s, ""));
    	if(answer.length() == 0) {
    		System.out.println("-1");
    	}else {
    		System.out.println(answer);
    	}
    }
    
    public static void simulate(Node start) { //일반
    	Queue<Node> q = new LinkedList<>();
    	
    	q.offer(start);
    	hashset.add(start.num);
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		long num = temp.num;
    		String str = temp.str;
    		
    		if(num == t) {
    			answer = str;
    			return ;
    		}
    		
    		long next = 0;
    		next = num * num;
//    		System.out.println("next:"+next);
    		
    		if(!hashset.contains(next)) {
    			hashset.add(next);
    			q.offer(new Node(next, str + "*"));
    		}
    		
    		next = num + num;
    		if(!hashset.contains(next)) {
    			hashset.add(next);
    			q.offer(new Node(next, str + "+"));
    		}
    		
    		next = num - num;
    		if(!hashset.contains(next)) {
    			hashset.add(next);
    			q.offer(new Node(next, str + "-"));
    		}
    		
    		if(num != 0) {
        		next = 1;
        		if(!hashset.contains(next)) {
        			hashset.add(next);
        			q.offer(new Node(next, str + "/"));
        		}    			
    		}

    		
    		
    	}
    }
    
    
}

class Node{
	long num;
	String str;
	public Node(long num, String str) {
		this.num = num;
		this.str = str;
	}
}

 

 

처음에 visited를 활용한 코드. 이렇게 할경우, Math.sqrt로 곱하기 이후에도 값이 올바르게 나오게하기 위한 처리

하지만 ArrayIndexOutofExcpeiton 이 뜹니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	public static int s, t;
	public static int MAX = 100000000;
	public static String answer="";
	public static boolean[] visited = new boolean[1000000000];
    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());
    	
    	simulate(new Node(s, ""));
    	System.out.println(answer);
    }
    
    public static void simulate(Node start) { //일반
    	Queue<Node> q = new LinkedList<>();
    	
    	q.offer(start);
    	visited[start.num] = true;
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int num = temp.num;
    		String str = temp.str;
    		
    		if(num == t) {
    			answer = str;
    			return ;
    		}
    		
    		int next = 0;
    		next = num * num;
    		System.out.println("next:"+next);
    		
    		if(visited[next] == false && next >= 1 && next <= Math.sqrt(MAX) ) {
    			visited[next] = true;
    			q.offer(new Node(next, str + "*"));
    		}
    		
    		next = num + num;
    		if(visited[next] == false && next >= 1 && next <= MAX) {
    			visited[next] = true;
    			q.offer(new Node(next, str + "+"));
    		}
    		
    		next = num - num;
    		if(visited[next] == false && next >= 1 && next <= MAX) {
    			visited[next] = true;
    			q.offer(new Node(next, str + "-"));
    		}
    		
    		if(num != 0) {
        		next = 1;
        		if(visited[next] == false && next >= 1 && next <= MAX) {
        			visited[next] = true;
        			q.offer(new Node(next, str + "*"));
        		}    			
    		}

    		
    		
    	}
    }
    
    
}

class Node{
	int num;
	String str;
	public Node(int num, String str) {
		this.num = num;
		this.str = str;
	}
}