알고리즘 풀이 - 백준 14395(4연산, 그래프(BFS))

 

관련글

 

그래프 관련 포스팅은 여기를 참조
DFS 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

4개의 연산으로 A → B로 변환 가능한 최소의 연산의 경우를 사전 순으로 가장 앞서는 1개만 출력하는 문제

 

 

2. 풀이

 

각 연산은 다음과 같다.

① * 연산 : S = S*S
② + 연산 : S = S + S = 2xS
③ - 연산 : S = S - S = 0
④ / 연산 : S = S / S = 1

 

여기서 처음에 단순 BFS로 모든 숫자를 탐색하여 가능한 연산 중 가장 적은 방식으로 연산하는 경우를 찾고자 할 수 있다.

그러나 다시 문제를 보면 최대 탐색 가능 숫자가 $10^9$이다. 즉, 10억이다.. 그럼 단순히 집합(Set) 혹은 배열을 통해 탐색이 완료된 숫자를 체크하고자 하면 어떻게 될까?

무조건 메모리 초과가 발생할 수밖에 없다.(메모리가 충분해도 시간 초과도 발생함) 따라서 더 효율적인 연산을 할 필요가 있다.

 

효율적으로 어떻게 풀 수 있을까? 실제로 이 문제는 2가지의 연산만 체크하면 된다. 그 2가지는 *, + 연산이다.

왜냐면 -, / 연산은 어떤 숫자에서 수행하든 0, 1이 되기 때문이다.

 

따라서, 처음에 1회만 체크를 한다면 이후에는 전혀 체크할 필요가 없게 된다!

그러면 우리는 더욱 중요한 사실을 알 수 있다. *, + 연산만 수행한다면 값은 계속 커지기만 할 것이므로 현재 탐색 중인 숫자가 목표 숫자보다 이미 커진 경우 추가 탐색이 불 필요하다는 것이다.

 

이를 이해한 상태에서 아래 코드를 보자.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

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

public class Main{
    static long s;
    static long t;
    static String[] oper = {"*", "+"};
    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());
        
        // 이미 같은 숫자라면 탐색이 불필요하다.
        if(s == t){
            System.out.println(0);
            return;
        }

        // 목표 숫자가 0이라면 - 연산만으로 정답이 구해진다.
        if(t == 0){
            System.out.println("-");
            return;
        }
        
        // 목표 숫자가 0이라면 / 연산만으로 정답이 구해진다.
        if(t == 1){
            System.out.println("/");
            return;
        }

        Queue<Num> q = new LinkedList<>();
        
        // *, +, / 연산의 경우를 초기로 지정하여 BFS를 통해 다음 탐색을 수행한다.
        // -연산은 0에서 어차피 값이 변할 수 없으니 체크할 필요가 없다.
        q.offer(new Num(s*s, "*"));
        q.offer(new Num(s*2, "+"));
        q.offer(new Num(1, "/"));

        // 이미 체크 완료한 숫자인지 체크하기 위한 Set
        HashSet<Long> set = new HashSet<>();
        
        // BFS 수행 코드
        while(!q.isEmpty()){
            Num c = q.poll();
            
            // 목표 숫자에 도달했다면 명령어 반환
            if(c.num == t){
                System.out.println(c.oper);
                return;
            }
            
            // 이미 더 큰 숫자가 되었다면 연산 불필요
            if(c.num > t){
                continue;
            }

            for(int i=0; i < 2; i++){
                // 다음 숫자를 찾는다.(+, * 연산만 수행)
                long next = oper(c.num, i);
                
                // 다음 숫자가 불가한 경우이거나, 이미 체크했다면 넘어간다.
                if(next == -1 || set.contains(next)) continue;
                set.add(next);
                q.offer(new Num(next, c.oper + oper[i]));
            }
        }
        
        // 위에서 반환되지 않았다면 불가한 경우이므로 -1 반환
        System.out.println(-1);
        br.close();
    }

    private static long oper(long num, int o){
        if(o == 0){
            // 1인 경우에는 *연산이 의미가 없다.
            if(num*num > t || num == 1) return -1;
            return num*num;
        } else {
            // 2인 경우에는 *연산으로 이미 4를 체크 중이므로 추가 체크가 불 필요하다.
            if(num*2 > t || num == 2) return -1;
            return num*2;
        }
    }
}

class Num{
    long num;
    String oper;
    public Num(long num, String oper){
        this.num = num;
        this.oper = oper;
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.