[백준] 12852번 - 1로 만들기 2 (Silver 1)

문제 링크

백준 12852번 - 1로 만들기 2 (Silver 1)

문제 설명

정수 N을 아래의 세 가지 연산만 사용해서 1로 만들려고 한다.

1. X가 3의 배수이면 X를 3으로 나눈다.
2. X가 2의 배수이면 X를 2로 나눈다.
3. X에서 1을 뺀다.

이 때, 필요한 최소 연산의 수와 그 과정(여러가지가 가능하다면 한개만)을 출력한다.

정답 코드 및 설명

X와 X/3(X가 3의 배수인 경우), X/2(X가 2의 배수인 경우), X-1을 연결된 노드로 생각한다.
BFS를 수행하면 최소 연산의 수를 구할 수 있다.
연산 과정을 기록하기 위해, BFS를 수행할 때 도착한 노드의 직전 노드를 같이 기록한다.

import java.io.*;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class BOJ12852 {
    final static int MAX = 1000001;
    int n;
    HashMap<Integer, Node> map = new HashMap<>();

    class Node {
        int before, dist;

        Node(int before, int dist) {
            this.before = before;
            this.dist = dist;
        }
    }

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
    }

    void bfs() {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(n);
        map.put(n, new Node(MAX, 0));
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            if (curr == 1) break;
            int currDist = map.get(curr).dist;
            if (curr % 3 == 0 && !map.containsKey(curr / 3)) {
                queue.add(curr / 3);
                map.put(curr / 3, new Node(curr, currDist + 1));
            }
            if (curr % 2 == 0 && !map.containsKey(curr / 2)) {
                queue.add(curr / 2);
                map.put(curr / 2, new Node(curr, currDist + 1));
            }
            if (curr > 1 && !map.containsKey(curr - 1)) {
                queue.add(curr - 1);
                map.put(curr - 1, new Node(curr, currDist + 1));
            }
        }
    }

    String path() {
        StringBuilder sb = new StringBuilder();
        int curr = 1;
        while (curr <= n) {
            sb.insert(0, curr + " ");
            curr = map.get(curr).before;
        }
        return sb.toString();
    }

    void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        sb.append(map.get(1).dist).append('\n');
        sb.append(path());
        bw.write(sb.toString());
        bw.close();
    }

    void solution() throws IOException {
        input();
        bfs();
        print();
    }

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