12851 숨바꼭질 2

12851 숨바꼭질 2

d배열 = 최소 몇번만에 도착 가능한지 기록

cnt배열 = 최소로 도착하는 경우의 수 기록

<Java>

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
    
    static int n,k;
    static int d[] = new int[100001];
    static int cnt[] = new int[100001];
    static final int dx[] = {1, -1};
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt();
        k = sc.nextInt();
        
        
        bfs();
        
        System.out.println(d[k] - 1 + "\n" + cnt[k] );
    }
    
    public static void bfs(){
        Queue<Integer> q = new LinkedList();
        q.add(n);
        d[n] = 1;
        cnt[n]= 1;
        
        while(!q.isEmpty()){
            int cur = q.poll(); //현재 위치
            
            int next = 0; //다음 위치
            for(int i = 0 ; i < 3 ; i++){
                if(i == 2){
                    next = cur * 2;
                }else{
                    next = cur + dx[i];
                }
 
                //범위 벗어나지 않는 곳만 탐색
                if(0 <= next && next <= 100000){
                    
                    //다음지점이 현재까지 찾은 최소값인 경우
                    if(d[next] == d[cur] + 1){
                        //현재 위치까지 최소값으로 오는 만큼의 경우의수를 더해준다.
                        cnt[next] += cnt[cur];
                        continue;
                    }
                    
                    
                    //한번도 방문하지 않았거나, 최소값 갱신 가능한경우
                    if(d[next] == 0 || d[next] > d[cur] + 1){
                        //d[next] 최소값으로 갱신
                        d[next] = d[cur] + 1;
                        //다음위치를 최소값으로 갱신하기때문에 현재위치까지 최소값으로 온 경우의 수를 저장해준다.
                        cnt[next] = cnt[cur];
                        q.add(next);
                    }
                }
            }
        }
    }
}
 
 

<c++>

#include <iostream>
#include <queue>
#define P pair<int,int>
using namespace std;
 
P visited[100001];
int n, k;
int dx[] = { 1,-1};
 
void bfs() {
    queue<int> q;
    q.push(n);
    visited[n].first = 1; //시간
    visited[n].second = 1; //방법의 수
 
    int next;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
 
        for (int i = 0; i < 3; i++) {
            if (i == 2) {
                next = cur * 2;
            }
            else {
                next = cur + dx[i];
            }
 
            if (next < 0 || next > 100000) continue;
 
            //다음점이 최소시간내 도착인 경우
            if (visited[next].first == visited[cur].first + 1) {
                visited[next].second += visited[cur].second;
                continue;
            }
 
            //최소값 갱신하는 경우
            if (visited[next].first == 0 || visited[next].first > visited[cur].first + 1) {
                visited[next].first = visited[cur].first + 1;
                visited[next].second = visited[cur].second;
                q.push(next);
            }
        }
    }
 
    cout << visited[k].first - 1 << "\n" << visited[k].second << endl;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin >> n >> k;
 
    bfs();
 
    return 0;
}