[BOJ 12851] 숨바꼭질2 (java)

1. 문제 : https://www.acmicpc.net/problem/12851

 

2. 풀이

가장 빠르게 특정 숫자->특정 숫자 방법 찾기

최단거리는 bfs가 빠르다는거 명심!

순서대로 bfs / dfs

 

3. 코드

dfs

package baekjoon;

import java.util.*;

public class Main {
    static int N,K;
    static int cnt;
    static int[] visited = new int[100005];
    static Map<Integer, Integer> hm = new HashMap<>();
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();

        cnt = 100005;

        Arrays.fill(visited, 100005);

        bfs(N, 0);
        System.out.println(cnt);
        System.out.println(hm.get(cnt));
    }

    public static void dfs(int x, int count){
        if(visited[x] >= count && cnt >= count){
            visited[x] = count;
            if(x==K){
                cnt = Math.min(cnt ,count);
                hm.put(cnt, hm.getOrDefault(cnt, 0)+1);
            }else if(x > 0 && x <= K/2+1){
                dfs(x*2, count+1);
                dfs(x+1, count+1);
                dfs(x-1, count+1);
            }
            else if(x > K/2+1 && x < K){
                dfs(x+1, count+1);
                dfs(x-1, count+1);
            }else if(x > K){
                dfs(x-1, count+1);
            }else if(x == 0){
                dfs(x+1, count+1);
            }
        }
    }
}

 

bfs

package baekjoon;

import java.util.*;

public class Main {
    static int N,K;
    static int count;
    static int[] min = new int[100001];

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();
        if(N==K){
            count = 1;
        }else{
            count = 0;
            bfs();
        }

        System.out.println(min[K]);
        System.out.println(count);
    }

    public static void bfs(){
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(N);

        while(!queue.isEmpty()){
            int cur = queue.poll();

            if(cur == K){
                count++;
            }else{
                int next;

                next = cur*2;
                if(next <= 100000 && cur != 0){
                    if(min[next] == 0 || min[next] >= min[cur]+1){
                        min[next] = min[cur]+1;
                        queue.offer(next);
                    }
                }

                next = cur+1;
                if(next <= 100000){
                    if(min[next] == 0 || min[next] >= min[cur]+1){
                        min[next] = min[cur]+1;
                        queue.offer(next);
                    }
                }

                next = cur-1;
                if(next <= 100000 && next >= 0){
                    if(min[next] == 0 || min[next] >= min[cur]+1){
                        min[next] = min[cur]+1;
                        queue.offer(next);
                    }
                }
            }
        }
    }
}