［BAEKJOON] 17071 숨바꼭질5 (C++)

백만년만에 문제 풀이

잔디가 빈 곳이 더 많다... 초심불망 마부작침!!!

 

문제 링크

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

17071번: 숨바꼭질 5

 

문제

수빈이의 위치 N, 동생의 위치 K가 주어진다.

동생은 1초에 한 번씩 이동하는데, 시작 시점으로부터 x초 지난 시점에서 동생은 x만큼 전진한다.

즉 동생의 위치는

1초 -> K + 1

2초 -> K + 1 + 2

3초 -> K + 1 + 2 + 3

 

수빈이가 동생을 찾는 최단 시간을 구하는 문제

 

풀이

문제를 풀기 위해서 핵심적인 아이디어는 다음과 같다.

1. 어떤 지점 X에 t초에 방문하였다면, t+2, t+4 ... 초 후에도 방문 가능하다. (앞 뒤로 이동 반복)

 

나는 여기서 홀수초 후에도 방문 가능한 케이스를 고려해서 코드를 짜보려 했는데, 불가능 했다. (ex 순간이동 후 뒤로 이동 등)

너무 케이스가 복잡하고 많으며, 완전한 논리라는 보장이 없었다.

 

시도해본 방법은

- 매 순간 동생의 위치로부터 N값을 찾는다 -> 약 700개의 위치에서 N을 BFS로 탐색한다 -> 시간초과

- 방문했던 곳도 다시 방문한다 -> 당연히 시간 초과

 

몇시간 고민하다가 결국 질문하기에 있는 힌트를 참고 했다.

이게 두번째 핵심 아이디어다.

 

2. 특정 지점에 방문한 시간을 짝수초와 홀수초로 구분한다.

만약 특정 지점 X에 홀수초 t1에 방문한 적이 있다면, 이후에 X지점을 홀수초에 방문하는 경우는 생각할 필요가 없다.

해당 지점에서 홀수초로 가능한 경우는 이미 탐색을 완료했다.

그리고 1번 논리에 의해서 탐색을 완료한 지점에 만약 동생과 만날 수 있는 지점이 있다면 정답에 반영이 되었을 것을 보장한다.

같은 원리로 짝수초인 경우에도 탐색 범위를 감소시켜 시간복잡도를 줄일 수 있다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <climits>
#define endl "\n"
#define MAX_LOC 500000

using namespace std;

int N, K;
int Time[505050];
bool Dest[505050];
bool Visited[505050][2];

queue<pair<int, int>> Q;

void Solve() {
    cin >> N >> K;
    int tmp = 0, ans = INT_MAX;
    while (K <= MAX_LOC) {
        Dest[K] = true;
        Time[K] = tmp;
        tmp++;
        K += tmp;     
    }
    
    Q.push({ N, 0 }); 
    Visited[N][0] = true;

    while (!Q.empty()) {
        int now = Q.front().first;
        int time = Q.front().second;
        Q.pop();

        if (Dest[now]) {
            if (Time[now] == time) {
                ans = min(ans, time); break;
            }
            else if (Time[now] > time && (Time[now]-time)%2 ==0) {
                ans = min(ans, Time[now]);
                continue;
            }
        }
        
        if (now * 2 <= MAX_LOC && Visited[now * 2][(time + 1) % 2] == false) {
            Visited[now * 2][(time + 1) % 2] = true;
            Q.push({ now * 2, time + 1 });
        }
        if (now +1 <= MAX_LOC && Visited[now + 1][(time + 1) % 2] == false) {
            Visited[now + 1][(time + 1) % 2] = true;
            Q.push({ now + 1, time + 1 });
        }
        if (now - 1 >= 0 && Visited[now - 1][(time + 1) % 2] == false) {
            Visited[now - 1][(time + 1) % 2] = true;
            Q.push({ now - 1, time + 1 });
        }
    }

    if (ans == INT_MAX) ans = -1;
    cout << ans;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("input.txt", "r", stdin);
    Solve();

    return 0;
}