BOJ 12851 숨바꼭질 2

www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

 

며칠 고민해봤는데 풀이 방법이 안 떠올라서 다른 블로그를 참고해서 풀었다.

두 개 정도의 풀이 방법이 있었는데 하나는 K로 가는 방법의 수를 배열 하나를 더 만들어서 접근하는 방법이고

다른 하나는 큐에서 팝 할 때 방문 체크를 해주는 방식이다.

 

첫 번째 방법은 시간이 항상 1씩 늘어난다는 것을 이용해서 d[next] == d[cur] + 1 이라면 cnt를 증가시키는 방법이다.

두 번째 방법은 현재 위치에서 팝 할때 방문처리를 해준다면 목적지 K는 항상 들어갈 수 있으므로

큐에 넣어주고 현 위치가 K이고 방문한 시간이 같다면 cnt를 증가시켜주는 방법이다.

 

 

#include <iostream>
#include <queue>
using namespace std;
 
int a[100001], cnt[100001], n, k;
bool vis[100001];
queue<int> q;
 
int main() {
    cin >> n >> k;
 
    vis[n] = true;
    q.push(n);
    cnt[n] = 1;
 
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for (int i : {cur - 1, cur + 1, cur * 2}) {
            if (0 <= i && i <= 100000) {
                if (!vis[i]) {
                    vis[i] = true;
                    q.push(i);
                    a[i] = a[cur] + 1;
                    cnt[i] = cnt[cur]; //이동가능하다면 현재까지의 경우의수 삽입
                } //현재 거리에서 1 더한값이 같다는 것은 이동 가능하다는 소리
                else if (a[i] == a[cur] + 1) cnt[i] += cnt[cur]; //경우의수 추가
            }
        }
    }
 
    cout << a[k] << endl;
    cout << cnt[k] << endl;
 
    return 0;
}

 

두 번째 코드

 

 

#include <iostream>
#include <queue>
using namespace std;
 
int n, k, cnt, time;
bool vis[100001];
queue<pair<int, int>> q;
 
int main() {
    cin >> n >> k;
 
    q.push({ n,0 });
    vis[n] = true;
 
    while (!q.empty()) {
        auto cur = q.front(); q.pop();
        vis[cur.first] = true;
        if (!time && cur.first == k) time = cur.second, ++cnt;
        else if (time == cur.second && cur.first == k) ++cnt;
        for (int i : {cur.first - 1, cur.first + 1, cur.first * 2}) {
            if (0 <= i && i <= 100000 && !vis[i]) q.push({ i,cur.second + 1 });
        }
    }
 
    cout << time << endl;
    cout << cnt << endl;
 
    return 0;
}