이것저것 개발 블로그

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

풀이)

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main_BJ_12851_숨바꼭질2 {
    static class location{
        int x;
        int time;
        public location(int x, int time){
            this.x=x;
            this.time=time;
        }
    }
    static int n, k, ans, method;
    static int[] visited = new int[100001];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();
        ans = 0;

        if(n==k) {
            System.out.println(ans);
            System.out.println(1);
        }
        else{
            method = bfs(n);
            System.out.println(ans+1);
            System.out.println(method);
        }
    }//main
    private static int bfs(int x){
        Queue<location> q = new LinkedList<>();
        visited[x]=0;
        q.offer(new location(x, 0));
        ans = Integer.MAX_VALUE;
        int way = 0;

        while(!q.isEmpty()){
            location now = q.poll();

            if(now.x-1 == k || now.x+1==k || now.x*2==k){
                if(ans == now.time)
                    way++;
                else if(ans > now.time){
                    ans = now.time;
                    way=1;
                }
            }

            if(now.x-1 >= 0 && (visited[now.x] == now.time+1 || visited[now.x]==0)){
                visited[now.x] = now.time+1;
                q.offer(new location(now.x-1, now.time+1));
            }
            if(now.x+1 <= 100000 && (visited[now.x] == now.time+1 || visited[now.x]==0)){
                visited[now.x] = now.time+1;
                q.offer(new location(now.x+1, now.time+1));
            }
            if(now.x*2 <= 100000 && (visited[now.x] == now.time+1 || visited[now.x]==0)){
                visited[now.x] = now.time+1;
                q.offer(new location(now.x*2, now.time+1));
            }

        }//while
        return way;
    }//bfs
}

해당 문제는 숨바꼭질 시리즈 문제 중에 2번째 문제다!!

문제는 맨날 bfs로 푼다는걸 까먹는다는 것이지....

이번 문제는 짧은 시간과, 해당 시간에 도착할 수 있는 경로의 개수를 세는 문제였다!

그래서 visited을 boolean 배열을 만들어서 풀었던 것과는 살짝 다르게 풀어야 한다.

방법은 visited 배열을 시간으로 만드는 것이다!!

무슨 말이냐,,, 해당 위치에 방문을 할 때 최소 시간을 저장해 두는 것이다.

따라서, 현재 최소 시간+1을 한 것(다음 칸으로 이동하려면 1초가 더해지니까!)이

저장해 둔 값과 같다면 queue에 저장해두고, 그렇지 않다면 queue에서 빼버린다.

최소 시간보다 더 크다면 어딘가를 더 들렀다 온 것이므로 볼 필요가 없기 때문!

그리고 이전에는 -1, +1, *2한 위치가 같다면 바로 탈출했지만,

이번에는 탈출하지 않고 몇 개의 경로가 있는지 체크해야한다.

따라서 현재 가지고 있는 가장 최소 시간이 같다면 경로를 더해주고,

더 작은 최소 시간이 있다면 경로를 1로 다시 초기화 시켜준다.

이러면 끝!