[12851번] 숨바꼭질 2

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS

2. Map STL

[1697번] 숨바꼭질 :: http://www.crocus.co.kr/627

위의 문제에서 단 하나만 더 추가되었다.

Map STL을 통해 cnt 즉 도착하기까지의 이동 횟수를 m[cnt]++로 두고 ret에는 가장 최단거리를 넣게하여

문제를 해결 할 수 있다.

물론 Map STL을 쓰지 않고 배열하나를 두고 arr[cnt]++로도 해결이 가능하다.

하지만 많은 공간 낭비를 방지하기위해 Map을 썼다. 

소스 코드 : 

#include <cstdio>
#include <iostream>
#include <queue>
#include <limits.h>
#include <map>
 
using namespace std;
 
#define MAX 100000
 
typedef pair<int, int> pii;
queue <pii> q;
map<int, int> m;
 
int visit[200001];
 
int main()
{
    int pos, target;
    scanf("%d %d", &pos, &target);
 
    q.push(pii(0, pos));
 
    int ret = INT_MAX;
    int cnt = 0;
 
    if (pos == target)
        printf("0\n1");
    
    else
    {
        while (!q.empty())
        {
            int x = q.front().second;
            int cnt = q.front().first;
 
            q.pop();
            visit[x] = 1;
 
            if (x == target)
            {
                    m[cnt]++;
                    ret = min(ret, cnt);
            }
 
            if (x * 2 <= MAX && x * 2 >= 0 && visit[x * 2] == 0)
                q.push(pii(cnt + 1, x * 2));
 
            if (x - 1 >= 0 && x - 1 <= MAX && visit[x - 1] == 0)
                q.push(pii(cnt + 1, x - 1));
 
            if (x + 1 <= MAX && x + 1 >= 0 && visit[x + 1] == 0)
                q.push(pii(cnt + 1, x + 1));
 
        }
 
        printf("%d\n%d", ret, m[ret]);
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>