[백준 - 17071] 숨바꼭질 5 - C++

분류: BFS /

 

문제

문제 링크

문제 설명

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 동생은 항상 걷기만 한다. 동생은 항상 매 초마다 이동을 하며, 이동은 가속이 붙는다. 동생이 이동하는 거리는 이전에 이동한 거리보다 1을 더한 만큼 이동한다. 즉, 동생의 처음 위치는 K, 1초가 지난 후 위치는 K+1, 2초가 지난 후 위치는 K+1+2, 3초가 지난 후의 위치는 K+1+2+3이다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 동생을 찾는 위치는 정수 좌표이어야 하고, 수빈이가 0보다 작은 좌표로, 50만보다 큰 좌표로 이동하는 것은 불가능하다.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 수빈이가 동생을 찾을 수 없거나, 찾는 위치가 500,000을 넘는 경우에는 -1을 출력한다.

 

풀이

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

bool vis[500001][2];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N, K; cin >> N >> K;
    queue<int> Q;
    vis[N][0] = true;
    Q.push(N);
    for(int sis=K, time=0; sis<500001; sis += ++time) {
        if(vis[sis][time & 1]) {
            cout << time;
            return 0;
        }
        int size = Q.size();
        while(size--) {
            int x = Q.front(); Q.pop();
            for(int nx : { 2*x, x+1, x-1 }) {
                if(nx < 0 || nx > 500000) continue;
                if(vis[nx][!(time & 1)]) continue;
                vis[nx][!(time & 1)] = true;
                Q.push(nx);
            }
        }
    }
    cout << -1;
}

20분도 안 돼서 풀고 시간초과 떠서 2시간 넘게 고민했던 것 같다.

`vis`없이 풀었다가 시간초과를 받고 현재 큐에 저장된 값이 중복되지 않도록 `vis`를 만들었더니 73% 정도에서 시간초과를 받았다. 

매 턴에서도 최적화가 필요했고 +1 -1로 진동하는 것을 어떻게 할 수 있지 않을까 고민하다 `vis`를 두 개를 만드는 방법을 생각했다.

• 동생이 범위를 벗어나기 전까지 수빈이가 동생을 찾아다닌다.(`sis < 500001`)
  • `vis[ i ][time & 1]`은 현재시간(`time`)에 수빈이가 `i`위치에 있을 수 있는 지를 의미한다.
  • 수빈이와 동생이 만났다면 시간을 출력하고 종료한다. (`vis[ sis ][time & 1]`)
  • BFS 순차 실행으로 1초 후 수빈이의 다음 위치를 계산한다.(`vis[ i ][!(time & 1)]`)

이 코드에서 중요한 부분은 `Q.pop`시 `vis = false`로 수빈이의 이전 위치를 없애주지 않는 것이다.

수빈이의 이전 위치를 release하지 않아도 되는 이유는 배열을 두 개를 쓰기 때문이다.

배열을 두개 쓰는 이유는 수빈이의 위치는 짝수 시간끼리와 홀수 시간끼리 관계를 갖기 때문이다.

t초 후 가능한 수빈이의 위치 집합을 P_t라고 할 때, 항상 P_t-2 ⊂ P_t이다.

집합 P의 모든 원소는 `+1 -1`, `-1 +1`로 진동하기 때문에 2초 후 다시 돌아오게 된다. 이때 연속된 2개의 연산 순열 6개 중 진동 연산 2개를 제외한 4개의 연산으로 P는 확장되기만 하고 축소되지 않는다.

따라서 `vis`배열에서 수빈이의 이전 위치를 release하지 않고 큐에는 새로운 위치만 들어가기 때문에 시간과 메모리를 절약할 수 있다.

 

# 첫번째 오답(vis 사용하지 않음) -> 메모리 초과

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N, K; cin >> N >> K;
    int dist = 0;
    queue<int> Q;
    Q.push(N);
    for(int k=K; k < 500001; k += ++dist) {
        int size = Q.size();
        while(size--) {
            int x = Q.front(); Q.pop();
            if(x == k) {
                cout << dist;
                return 0;
            }
            for(int nx : {2*x, x+1, x-1}) {
                if(nx<0 || nx>500000) continue;
                Q.push(nx);
            }
        }
    }
    cout << -1;
}

현재 위치로 다시 돌아올 수 있기 때문에 vis를 사용하지 않았다. 이때 큐에는 같은 위치가 중복으로 들어가게 된다. 

 

# 두번째 오답(현재 위치만 중복 제거) -> 78% 시간초과

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

int vis[500001];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N, k; cin >> N >> k;
    int time = 0, mark = 1;
    queue<int> Q;
    Q.push(N);
    vis[N] = mark;
    while(k < 500001) {
        int size = Q.size();
        while(size--) {
            int x = Q.front(); 
            if(x == k) {
                cout << time;
                return 0;
            }
            Q.pop();
            for(int nx : {2*x, x+1, x-1}) {
                if(nx<0 || nx>500000) continue;
                if(vis[nx] == mark) continue;
                Q.push(nx);
                vis[nx] = mark;
            }
        }
        k += ++time;
        mark++;
    }
    cout << -1;
}

`vis`를 사용해 현재 큐에 중복이 발생하지 않도록 했다. 

`mark`를 이용해 `vis`를 덮어 씌워 매번 방문을 초기화하지 않도록 했다.

tag: 다른 값으로 방문 표시