알고리즘 :: 백준 :: BFS :: 13913 :: 숨바꼭질4

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

문제접근

• 기존 숨바꼭질 1, 2 문제와 동일한 조건을 가지고 있지만 이번에는 도착지점까지 가는 경로까지 나타내야 하는 문제다.
• 전역탐색하는 BFS 특성에 의해 최적해를 향하는 과정(경로)을 나타내기는 쉽지 않다.
• 그러므로 우리는 최적해에서 다시 시작지점으로 돌아가는 백트래킹을 사용해야 한다.
• 올바른 백트래킹을 하기 위해 기존 문제에는 없던 from배열을 만들었다.
  • from 배열의 i번째 인덱스에는 해당 정점에 오기 직전의 정점 번호가 기재된다.

코드

#include <iostream>
#include <queue>
using namespace std;

static constexpr int MAX = 100001;
static int subin, brother, map[MAX], from[MAX], dist[MAX];
static bool isVisited[MAX];

void backTracking(int subin, int pos) {
    // subin (출발지점) 까지 백트랙킹 한다.
    if (subin != pos) backTracking(subin, from[pos]);
    cout << pos << ' ';
}

void solve() {
    queue<int> q;
    q.push(subin);
    isVisited[subin] = true;
    dist[subin] = 0;

    while(!q.empty()) {
        int pos = q.front(); q.pop();
        int goPos = pos + 1, backPos = pos - 1, telePos = pos * 2;
        // 한 칸 앞으로 전진하는 경우
        if (goPos < MAX && isVisited[goPos] == 0) {
            q.push(goPos);
            isVisited[goPos] = true;
            dist[goPos] = dist[pos] + 1;
            from[goPos] = pos;
        }
        // 한 칸 뒤로 후진하는 경우
        if (backPos >= 0 && isVisited[backPos] == 0) {
            q.push(backPos);
            isVisited[backPos] = true;
            dist[backPos] = dist[pos] + 1;
            from[backPos] = pos;
        }
        // 2배 앞으로 순간이동 하는 경우
        if (pos != 0 && telePos < MAX && isVisited[telePos] == 0) {
            q.push(telePos);
            isVisited[telePos] = true;
            dist[telePos] = dist[pos] + 1;
            from[telePos] = pos;
        }
    }
    cout << dist[brother] << '\n';
    backTracking(subin, brother);
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> subin >> brother;
    solve();
}

50% 지점에서 메모리 초과 오류가 나는 경우

• 0 5 를 입력하면 메모리 초과가 나는 경우일 것이다.
• 원인은 백트래킹 과정에서 무한 loop를 돌기 때문이다.
• 
• 만일, isVisited 배열을 구현하지 않았거나, dist 배열의 초기값이 -1이 아니라 0이라면 0 5 테스트 케이스에서 from배열을 아래와 같이 나온다.
• 
• 1번 인덱스와 2번 인덱스에서 계속 재귀를 call하는 무한 루프가 생기고만다.
• 따라서 dist 배열의 초기값을 -1로 memset()한 뒤 방문 여부를 -1값으로 판단하거나, isVisited배열을 구현하거나, 둘 중 편한 방법을 꼭 사용하자.

결과