[백준 12851] 숨바꼭질2 -JAVA // le_effort//

 

기존 숨바꼭질 문제와 다른점은 중복 방문을 부분적으로 허용해야 한다는 것이다

 

예를 들어서 1->2->3 을 갈 때

 

1, 1*2 , 1*2+1 = 3번

1, 1+1 1+1+1 = 3번

 

이런 식으로 +, -, * 를 다른 경우의 수로 쳐줘야 한다.

 

하지만 최소시간을 구하는 것 이므로 

4를 간다 치면

1, 1*2 , 2*2 를 하면 3번만에 갈 수 있지만

1, 1+1 ,1+1+1 ,1+1+1+1 는 4번이 걸림으로 고려를 하지 않아줘도 된다

 

즉 같은 시간대 (코드에선 반복문 내에서)만 처리를 해주면 된다.

 

if(!visited[n]) 이라면

visited[n] = true

q.add(n) 이런 진행이 아니라

 

일단 큐에 집어넣고 

큐에서 뺏을때 visited 처리를 해주면 된다

 

import java.io.*;
import java.util.*;
public class Main {
    static int n,k;
    static int cnt = 0;
    static int min = Integer.MAX_VALUE;
    static boolean visited[];
    static int dx[] = {1,-1};
    static ArrayList<Integer>list = new ArrayList<>();
    static Queue<Node> q = new LinkedList<>();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);
        k = Integer.parseInt(t[1]);
        q.add(new Node(n,0));
        visited = new boolean[100001];
        visited[n] =true;
        bfs();
        
        for(int i=0; i<list.size(); i++) {
            min = Math.min(min, list.get(i));
        }
        for(int i=0; i<list.size(); i++) {
            if(min == list.get(i)) {
                cnt++;            }
        }
        if(n==k) {
            System.out.println(0);
            System.out.println(1);
        }
        else {
        System.out.println(min);
        System.out.println(cnt);
        }
    }
    public static void bfs() {
        while(!q.isEmpty()) {
            Node a = q.poll();
            visited[a.x] = true;
            for(int i=0; i<3; i++) {
                int tmp=a.x;
                if(i==2) {
                    tmp = a.x*2;
                    if(tmp>=0 && tmp<=100000) {
                        if(tmp == k) {
                            list.add(a.cnt+1);
                        }
                        else {
                            if(!visited[tmp]) {
                                //visited[tmp]=true;
                                q.add(new Node(tmp,a.cnt+1));
                            }
                        }
                    }
                }
                else {
                    tmp = a.x+dx[i];
                    if(tmp>=0 && tmp<=100000) {
                        if(tmp == k) {
                            list.add(a.cnt+1);
                        }
                        else {
                            if(!visited[tmp]) {
                                //visited[tmp]=true;
                                q.add(new Node(tmp,a.cnt+1));
                            }
                        }
                    }
                }
            }
        }
    }
}
class Node{
    int x,cnt;
    Node(int x , int cnt){
        this.x=x;
        this.cnt=cnt;
    }
}