[백준] 27440번 - 1로 만들기 3 [Java]

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

 

[백준] 27440번 - 1로 만들기 3 [Java]

[백준] 27440번 - 1로 만들기 3 [Java]

---

1.  아이디어

 

이전 1로 만들기 문제에서 수의 범위가 커진 문제로 BFS와 Set을 활용한 방문체크로 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 1463번 - 1로 만들기 [Java])

---

2. 문제풀이

 

수의 범위가 int형을 넘어가므로 배열로 방문 체크를 진행할 수 없어 Set을 활용해서 방문 체크를 진행했다.

다이나믹 프로그래밍 풀이도 시도했는데 최적화하려는 노력에도 시간초과가 발생했다.

---

3. 코드

 

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

public class Main {

    private static class Node implements Comparable<Node> {
        long num;
        int cnt;

        public Node(long num, int cnt) {
            this.num = num;
            this.cnt = cnt;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.cnt, o.cnt);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        long N = Long.parseLong(br.readLine());

        System.out.println(bfs(N));
    }

    private static int bfs(long N) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        Set<Long> visited = new HashSet<>();

        pq.add(new Node(N, 0));
        visited.add(N);

        while (!pq.isEmpty()) {
            Node item = pq.poll();

            if (item.num == 1) return item.cnt;

            if (item.num % 3 == 0 && !visited.contains(item.num / 3)) {
                pq.offer(new Node(item.num / 3, item.cnt + 1));
                visited.add(item.num / 3);
            }
            if (item.num % 2 == 0 && !visited.contains(item.num / 2)) {
                pq.offer(new Node(item.num / 2, item.cnt + 1));
                visited.add(item.num / 2);
            }
            if (!visited.contains(item.num - 1)) {
                pq.offer(new Node(item.num - 1, item.cnt + 1));
                visited.add(item.num - 1);
            }
        }

        return -1;
    }

}

---

4. 후기