백준 12851 숨바꼭질2 [c++]

백준 12851

해결방안

• 5부터 시작해 17로 가는 (X-1, X+1, X*2 를 이용해) 최단거리를 구하는 문제이다.
  최단거리를 구할땐 역시 BFS...

• 일차원 배열 a를 선언하고 (X-1, X+1, X*2) 를 전부 적용해 뻗쳐나가고 해당 위치에 대한 최단거리를 visited에 저장한다

• 17로 가는 가장 빠른 시간이 몇 가지 되는지도 저장해야 하기 때문에 방문 했지만 최단거리라면 cnt[17] 배열의 값을 계속 증가시킨다

#include<bits/stdc++.h>
using namespace std;

const int MAX = 100005;
int visited[MAX];
int n, k;
queue<int> q;
int cnt[MAX];
int main() {
    cin >> n >> k;
    if(n == k) {
        puts("0"); puts("1");
        return 0;
    }
    q.push(n);
    cnt[n] = 1;
    while(q.size()) {
        int now = q.front();
        q.pop();
        for(int move : {now + 1, now-1, now * 2}) {
            if(move < 0 || move > MAX) continue;
            if(!visited[move]) {
                visited[move] = visited[now] + 1;
                q.push(move);
                cnt[move] += cnt[now];
            }else if(visited[now] + 1 == visited[move]) {
                cnt[move] += cnt[now];
            }
        }
    }
    cout << visited[k] << '\n' << cnt[k];
}

안일했던 점

 if(n == k) {
        puts("0"); puts("1");
        return 0;
    }

이 코드를 추가하지 않아 계속 오답이 되었다.. ㅠㅠ
항상 테스트 케이스를 잘 생각하는 습관을 길러야겠다