13549 숨바꼭질 3

13549 숨바꼭질 3 (c++)

문제

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

접근 방식

BFS, PQ

1. 처음엔 N부터 시작해서 *2는 cost + 0, +1, -1은 cost + 1을 처리하는 재귀함수를 만들었었다.
   1. 재귀함수가 *2를 먼저 처리해도, *2가 MAX_SIZE(100’000)을 넘어가는 수부터는 +1, -1을 처리하기 시작해서 시간초과
   2. 이 때 (*2를 먼저(우선) 처리하고 +1, -1을 나중에 처리하는 순서(방법)을 찾았어야했다.)
2. 다음엔 먼저 *2를 0부터 MAX_SIZE까지 처리하고, 다시 0부터 MAX_SIZE 까지 순회하면서 +- i를 했을 때 cost[now] + i보다 큰 수가 있으면 수정하는 식으로 처리했다.
   1. 이유는 모르겠지만 실패
3. 질문글들의 반례가 다 맞았었는데 테스트에서는 실패를 했고, 결국 풀이법이 PQ를 사용한 BFS라는 힌트를 보았다.
4. N부터 BFS를 진행하여 *2, -1, +1을 PQ에 집어넣고 cost가 낮은 순서대로 꺼내어 다시 BFS를 진행하는 식으로 풀었다. (성공)

문제 풀이

#include <cstdio>
#include <queue>
#define MAX_SIZE 100000
using namespace std;
int N, M, cost[MAX_SIZE + 1] = {};
void BFS()
{
    queue<int> q;
    cost[N] = 1;
    q.push(N);
    while (!q.empty())
    {
        int pos = q.front(); q.pop();
        
        if (pos == M)
        {
            printf("%d\n", cost[pos] - 1);
            return;
        }
        if ((pos - 1 >= 0) && (cost[pos-1] == 0 || cost[pos-1] > cost[pos] + 1))
        {
            cost[pos-1] = cost[pos] + 1;
            q.push(pos - 1);
        }
        if ((pos + 1 <= MAX_SIZE) && (cost[pos + 1] == 0 || cost[pos + 1] > cost[pos] + 1))
        {
            cost[pos + 1] = cost[pos] + 1;
            q.push(pos + 1);
        }
        if ((pos * 2 <= MAX_SIZE) && (cost[pos * 2] == 0 || cost[pos * 2] > cost[pos]))
        {
            cost[pos * 2] = cost[pos];
            q.push(pos * 2);
        }
    }
}

int main()
{
	scanf("%d %d", &N, &M);
	BFS();
}

다시 생각해 볼 점

1. PQ를 이용하였지만, push에서 시간을 많이 잡아먹어서 최적화 방법을 찾아봤다.
2. 시간대가 적게 나온 분의 코드를 살펴보니 아래와 같은 차이점이 있었다.
   1. BFS를 다 돌리지 않고, 현재 탐색 위치가 M이면 해당값을 출력하고 return
   2. PQ 대신 일반 큐를 사용하되, 큐에 들어가는 순서를 직접 정해줌.
      1. -1 먼저 조건 검사후 삽입
      2. 그 후, +1을 조건 검사 후 삽입
      3. 마지막으로 *2를 조건 검사 후 삽입
3. 2개를 적용했더니 시간이 0ms로 단축되었다. (PQ는 우선순위를 체크해야해서 push에 시간이 많이 소모된다는 점을 기억하자.)