12851 : 숨바꼭질 2 - BFS

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

12851번: 숨바꼭질 2

 

문제요약

1칸 좌우 이동, 2배 이동이 가능할 때, 도착점으로 가는 최단 시간과 경우의 수 구하기.

 

난이도

Gold 4

---

풀이 포인트

• bfs 응용
  • 방문한 적 없다면 이동 시간 누적
• cnt 배열
  • 경로의 수는 지금까지의 경로의 수에 누적해주는 방식
  • 방문한 적 없다면 현재 위치까지의 경우의 수 + 다음 정점의 경우의 수
  • 방문한 적 있고, 현재 노드에서 간 적 있는 경로라면 또 경우의 수 누적

• 동작 3가지를 배열로 만들어 순차 반복시키는 방법

   for (int next : {now - 1, now + 1, now * 2})

---

REVIEW

 

우선, 재귀함수와 최솟값 갱신 및 최솟값 카운트로 생각하고

x -1, x+1, 2*x 실행하며 도착점에 도착하면 재귀를 멈추는 식의 구현을 했다.

어찌저찌 테스트 케이스는 통과했지만 시간 초과가 났다.

맞는 코드인지 판단조차 할 수 없었고 이미 시간을 너무 많이 투자한지라 답안을 봤다.

 

모든 경로를 탐색하며 최솟값을 갱신하는 것이 아니라,

bfs로 최단 거리로만 탐색해 가며 경로의 경우의 수를 누적하고 도착지에 누적되어 있는 경우의 수를 이용하는 방식.

새로운 것을 배웠다.

 

그런데 답안 코드에서는 현재  위치가 도착지에 다다랐을 때 반복을 멈추지 않고

조건 범위 max까지 경로들을 구해둔다. 그래서 디버깅 코드가 몇 만까지 늘어나는 것을 보고

우선은 도착지의  2배까지로 줄여 디버깅을 진행해봤는데

꼭  전수 검사를 해야하는 이유가 있을지도 한 번 생각해봐야겠다.

---

CODE

// 디버깅 이해 코드
#include <bits/stdc++.h>
using namespace std;

const int MAX = 200000;
int visited[MAX + 4];
long long cnt[MAX + 4];

int main()
{
    int n, m;
    cin >> n >> m;


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

    visited[n] = 1;
    cnt[n] = 1;

    queue<int> q;
    q.push(n);

    while (!q.empty())
    {
        int now = q.front();
        q.pop();

        cout << "현재 " << now <<'\n';

        for (int next : {now - 1, now + 1, now * 2})
        {
            if (0 <= next && next <= m+m)
            {
                if (!visited[next])
                {
                    cout << "다음은 " << next <<"이고, 방문한 적 없어서 방문배열에 이동 누적"<< '\n';

                    q.push(next);
                    visited[next] = visited[now] + 1;
                    cnt[next] += cnt[now];
                    cout  << next <<"까지 누적된 이동은 " <<visited[next] << '\n';
                    cout << next << "까지의 경로는 " << cnt[next] <<"가지" << '\n';
                }
                else if (visited[next] == visited[now] + 1)
                {
                    cout << "다음은 " << next << "이고, 그리로 이동한 적이 있어서 경로 경우의 수만 갱신" << '\n';
                    cnt[next] += cnt[now];
                    cout << next << "까지의 경로는 " << cnt[next] << "가지" << '\n';
                }
            }
        }
    }
    cout << visited[m] - 1 << '\n';
    cout << cnt[m] << '\n';
    return 0;
}