[자바] 백준 14395 - 4연산 (java)

 문제 : boj14395

---

 

필요 알고리즘 개념

• 너비 우선 탐색 (bfs)
  
  • BFS로 풀 수 있다!

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  BFS를 모른다면 'BFS 알고리즘 (너비 우선 탐색)' 글을 참고해보자.

우선 걸러낼 수 있는걸 먼저 생각해보자.

 

1. s = s - s; 연산의 경우 무조건 0이 되며, 이후 *, +, / 뭘 해도 0 이외로 벗어날 수 없다. 근데 t는 1 이상으로 입력이 주어진다. 따라서 그냥 버리면 된다. 나올 일이 없다.

 

2. s = s / s; 의 경우 s가 몇이든 항상 1이 된다. 그럼 연산 중간에 1로 내려가는 것이 의미가 있을까? 맨 처음에 '/'가 나올 때만 의미가 있다.

 

3. 그럼 남은건 +와 * 뿐이다. s에서 시작해서 +와 * 연산을 각가 붙여가며 t까지 도달해보면 된다. '2'에 따라 '/'는 처음에만 의미가 있으므로 처음에만 한 번 시도해주면 된다. BFS 자체는 일반적인 BFS와 다를바 없으므로 별도로 설명하지 않아도 될 것 같다.

  (TMI) 근데 이것만 해도 사실 n번의 연산이 필요하다면 O(2^n) 이라는(n번에 걸쳐 +와 *중 하나를 선택하는 경우의 수) 무시무시한 시간복잡도가 나온다. 대략 n이 28을 넘어가게 되면  그렇다면 통과가 가능한지 우선 봐야 한다. 우선 '*'의 연산의 경우엔 간단하다. s = 2에서 출발해 5번만 연산해봐도 42억이다. *보다 느린 +가 문제가 될건데, s=1에서 시작할 때 29번을 연산해야 t의 최대값인 10억을 넘는다.

  근데 백트래킹 개념까지 넣어보자면 결국 t를 초과하는 경우는 버리면 된다. 그리고 *연산이 가능한 최대 시점이래봐야 31622까지이다(31622^2 = 약10억). 그렇다면 31622까지 + 연산으로 가는 경우는 15번으로 된다. 그 이후로는 +연산만 가능하므로 O(2^15) 이하로 가능하다. 실제론 더 작게 나온다.

 

4. 지나온 루트에 대해 연산을 순서대로 출력하는건 어려울 수 있다. 사실 '3'에서 TMI 부분에서 써놨듯이 실제로 연산 횟수가 매우 작기 때문에 그냥 String으로 매번 유지해도 되지만 이쁘지 않다.

  내 경우엔 아래처럼 처리했다.

class Node {
    long num;	// 현재 숫자(
    char c;	// 현재 연산
    Node bf;	// 이전 노드를 가리키는 포인터
    public Node(long num, char c, Node bf) {
        this.num = num;
        this.c = c;
        this.bf = bf;
    }
}

...

while (!q.isEmpty()) {
    Node cur = q.poll();
    if (cur.num == t) {	// t에 도달한 경우
        StringBuilder sb = new StringBuilder();
        while (cur.bf != null) {	// 출발점은 cur.bf가 null이므로 역으로 타고들어간다.
            sb.append(cur.c);	// StringBuilder에 넣는다.
            cur = cur.bf;	// 역으로 이전 노드로 이동한다.
        }
        return sb.reverse().toString();	// 역순으로 출력해준다.
    }
	...
}

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public String bfs(long s, long t) {
        Set<Long> v = new HashSet<>();
        v.add(s);
        Queue<Node> q = new ArrayDeque<>();
        q.add(new Node(s, '\0', null));
        boolean divideChk = false;
        while (!q.isEmpty()) {
            Node cur = q.poll();
            if (cur.num == t) {
                StringBuilder sb = new StringBuilder();
                while (cur.bf != null) {
                    sb.append(cur.c);
                    cur = cur.bf;
                }
                return sb.reverse().toString();
            }

            long next = 1l*cur.num*cur.num;
            if (next <= t && !v.contains(next)) {
                v.add(next);
                q.add(new Node(next, '*', cur));
            }

            next = 2*cur.num;
            if (next <= t && !v.contains(next)) {
                v.add(next);
                q.add(new Node(next, '+', cur));
            }

            if (divideChk) continue;
            divideChk = true;
            next = 1;
            if (v.contains(next)) continue;
            v.add(next);
            q.add(new Node(next, '/', cur));
        }

        return "-1";
    }

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int s = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());
        if (s == t) {
            System.out.println(0);
            return;
        }
        if (t == 1) {
            System.out.println("/");
            return;
        }

        System.out.println(bfs(s, t));
    }
}

class Node {
    long num;
    char c;
    Node bf;
    public Node(long num, char c, Node bf) {
        this.num = num;
        this.c = c;
        this.bf = bf;
    }
}