[BOJ-12851]숨바꼭질2

이 문제도 [1697]숨바꼭질1 과 같은 BFS 인데, 이건 최소경로의 수가 몇개인지도 출력하는 문제이다. 

음..... 이문제는 연산은 다른 것이고 결과값이 같은 경우 

1(+) 2

1(*) 2

예로 들자면 이런 경우에 다른 경우가 되는 것인데 

이것을 어떻게 처리를 할 것인지에 대한 문제인 것으로 생각했다. 

각 방문하여 최단경로를 저장하는 것은 한번에 갱신하고 갱신된 정보를 가지고 Q에 넣을지 말지를 결정한다.

1. 갱신이 되지 않은 (-1, 초기상태) 일 때는 무조건 갱신하며, Q에 넣는다.

2. 갱신이 되었다면, 현재 위치한 곳의 최단경로 + 1 보다 크거나 같다면 재갱신하며, Q에 넣는다. 

음..... 2번에 조건 문이 크거나 같다면이 아니라 같다면으로 해도 될 것 같긴한데... 왜냐면 BFS 자체가 현재 경로수 +1 을 하기 때문에 

 현재 경로수+1 보다 큰 값이 들어가 있지는 않을테니까.... 저 조건은 같다면으로 수정해도 될 것 같다. 코드 제출하고서 든생각;;;;;; 다시 제출해보니 같다면 Q에 넣는다가 맞는것으로 생각된다;;;;

#include<cstdio>
#include<queue>
#include<memory.h>
using namespace std;
// 빠른(mini), 경로수(kind)
const int MAX = 100001;
int sta, fin, kind;
int mini = 0x0FFFFFFF;
int visited[MAX];
int main(){
    scanf("%d%d",&sta,&fin);
    memset(visited, -1, sizeof(visited));
    queue<int> q;
    q.push(sta);
    visited[sta] = 0;
 
    while(!q.empty()){
        int here = q.front(); q.pop();
        
        if(here == fin){
            if(mini >= visited[here]) mini=visited[here],kind++;
            else break;
        }
 
 
        if(here - 1 >= 0)
            if(visited[here-1] == -1 || (visited[here-1] == visited[here]+1) ) visited[here-1] = visited[here]+1, q.push(here-1);
        if(here + 1 < MAX)
            if(visited[here+1] == -1 || (visited[here+1] == visited[here]+1) ) visited[here+1] = visited[here]+1, q.push(here+1);
        if(2*here < MAX)
            if(visited[2*here] == -1 || (visited[2*here] == visited[here]+1) ) visited[2*here] = visited[here]+1, q.push(2*here);
    }
 
    printf("%d\n%d",mini,kind);
    return 0;
}