[13913] 숨바꼭질 4

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

13913번: 숨바꼭질 4

<문제>

BFS + 최적해 역추적을 요구하는, 좋은 문제이다.

문제 이름은 "숨바꼭질 4"지만 1~3을 모두 포함하는 문제는 아니다.

숨바꼭질 1 : 최적해
숨바꼭질 2 : 최적해+ 최적해의 개수
숨바꼭질 3 : 변형 BFS (1/2/4와는 성질이 다르다)
숨바꼭질 4 : 최적해 + 최적해 역추적

그렇기에 BFS를 연습하려면 2,3,4는 다 풀어봐야 하겠다. 좋은 문제이니 여러번 봐도 좋을듯 싶다.

입력으로 N과 K가 주어지고,

N에 +1, -1, *2의 연산을 최소로 가해 K를 만들면 된다. 사실 이문제는 역추적이 주로 문제가 된다.

 

path[]를 하나 만들어, 이 선형 자료구조에 '이전의 위치'를 저장할 것이다.

큐에 삽입할 모든 수를 하나의 정점으로 보고, 이 정점을 방문하기 직전에 방문한 노드의 번호를 저장한단 뜻이다.

실제로 최적해를 찾은 다음에는 최적해부터 시작위치 N까지 역으로 거슬러 올라올 것이다.

마지막 위치(K)는 그 이전의 노드번호를, 그 이전의 노드의 path에는 다시 그 이전의 노드번호를 저장하고

이 과정을 재귀나 반복문(보통 while로 한다)으로 구현하면 된다.

path를 애초에 전역으로 선언하거나, 0으로 초기화해두면

while(path!=0) -> 이전의 정점이 존재할동안 반복.. 이런식으로 작성이 가능하다.

그게 아니라면 while(cur이 N이 아닐동안)... 이렇게도 작성할 수 있고, 재귀함수로 작성하는것도 가능하다.

<소스코드>

#include<stdio.h>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
queue <pair<int, int>> q;
const int SIZE = 250001;
int n, k,cur,min_cnt,cnt;
bool visit[250003];
int path[250003];
 
int main(void) {
    scanf("%d %d", &n, &k);
    if (n == k) {
        printf("0\n%d", n);
        return 0;
    }
    if (n > k) {
        printf("%d\n", n - k);
        for (int i = n; i >= k; i--) {
            printf("%d ", i);
        }
        return 0;
    }
    q.push(make_pair(n, 0));
    visit[n] = true;
    while (!q.empty()) {
        cur = q.front().first;
        cnt = q.front().second;
        q.pop();
        if (cur == k) {
            min_cnt = cnt;
            break;
        }
        if (cur * 2 <= SIZE && !visit[cur * 2]) {
            q.push(make_pair(cur * 2, cnt + 1));
            visit[cur * 2] = true;
            path[cur * 2] = cur;
        }
        if (cur + 1 <= SIZE && !visit[cur + 1]) {
            q.push(make_pair(cur + 1, cnt + 1));
            visit[cur + 1] = true;
            path[cur + 1] = cur;
        }
        if (cur - 1 >= 0 && !visit[cur - 1]) {
            q.push(make_pair(cur - 1, cnt + 1));
            visit[cur - 1] = true;
            path[cur - 1] = cur;
        }
    }
    printf("%d\n", min_cnt);
    stack <int> s;
    int temp = k;
    path[n] = n;
    while (temp!=n) {
        int now = temp;
        s.push(now);
        temp = path[temp];
    }
    s.push(n);
    while (!s.empty()) {
        int now = s.top();
        s.pop();
        printf("%d ", now);
    }
    return 0;
}

52번~65번까지가 역추적이고, 그 외에는 숨바꼭질1과 동일하다