[백준 / BOJ] C++ 17071

#17071: 숨바꼭질 5

문제

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

설명

수빈(간단히 누나)은 다른 숨바꼭질처럼 +1, -1 또는 ×2를 이동할 수 있으며 1초가 걸립니다.
대신 동생은 1초에 1칸, 2초에 2칸, … N초에 N칸을 움직인다.
따라서 BFS 알고리즘을 사용하여 해결할 수 있습니다.

첫 번째 접근 방식은 각각에 대해 BFS를 수행하고(남동생은 실제로 하나만 이동하지만) 타임스텝으로 이동하고 언니가 이동할 때마다 여동생의 위치에 도달할 수 있도록 하는 것이었습니다.
그러나 71%가 TLE를 받았습니다.
그것을 풀기 위해 질문게시판을 뒤져보니… 정말 좋은 규칙과 아이디어를 발견했습니다.

이것은 당신의 여동생이 지나간 곳을 다시 지나갈 수 있다는 것을 의미합니다.
사실 그런 생각을 했고, 위에 구현을 할 때도 나름 적용을 했다.
하지만 끝없이 왔다 갔다 하며 홀수 시간에 도착하면 항상 홀수 시간에 방문할 수 있고, 짝수일 때도 마찬가지다.
따라서 홀수시간의 최초도착시간과 짝수시간의 최초도착시간을 별도로 기록한다.

따라서 2D 배열은 (위치) (홀수/짝수)로 변환됩니다.
BFS는 위치와 시간을 쌍으로 큐잉하여 수행됩니다.
위치 ×2, -1 및 +1에 대해서는 시간을 홀수/짝수로 기록하고 방문하지 않았거나 더 짧은 시간에 도달할 수 있는 시간을 기록합니다.

여동생의 현지 시간을 검색하여 여동생이 있는 장소에 홀수/짝수로 도착한 시간을 여동생이 도착한 시간과 비교하고, 여동생이 나중에 도착한 경우에는 여동생의 도착시간이 출력됩니다.
그와 별개로 남동생의 시간이 1씩 가고 남동생이 이동하며 다시 비교과정을 반복한다.
찾지 못하면 -1을 반환합니다.

너무 어렵다.
. 정신력과 체력이 많이 소모된다.
.

잘못된 코드

#include <bits/stdc++.h>
using namespace std;

int n, k, t = 0, flag = 0;
vector<int> visitedS(500001, 0), visitedB(500001, 0);
queue<int> qS, qB;

void bfsS() {
  int size = qS.size();
  while (size--) {
    int x = qS.front();
    qS.pop();
    vector<int> nxt{curr * 2, curr - 1, curr + 1};
    for (int next : nxt)
      if (next >= 0 && next <= 500000)
        if (visitedS(next) < t) {
          q.push(next);
          visitedS(next) = t;
        }
  }
}

void bfsB() {
  int x = qB.front();
  qB.pop();
  t++;
  if (x + t >= 0 && x + t <= 500000) {
    qB.push(x + t);
    visitedB(x + t) = visitedB(x) + 1;
  } else {
    flag = 1;
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> k;
  if (n == k) {
    cout << 0;
    return 0;
  }
  qS.push(n);
  qB.push(k);
  while (!
qB.empty()) {
    if (flag) {
      cout << -1;
      return 0;
    }
    bfsB();
    bfsS();
    int x = qB.front();
    if (x == 0)
      break;
    if (visitedS(x) == visitedB(x)) {
      cout << visitedS(x);
      return 0;
    }
  }
  cout << -1;
  return 0;
}

올바른 코드

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9

int n, k;
vector<vector<int>> sister(500001, vector<int>(2, INF));
vector<int> brother(500001, 0);

void bfs() {
  queue<pair<int, int>> q;
  q.push({n, 0});
  sister(n)(0) = 0;
  while (!
q.empty()) {
    int curr = q.front().first;
    int time = q.front().second;
    q.pop();
    vector<int> nxt{curr * 2, curr - 1, curr + 1};
    for (int next : nxt)
      if (next >= 0 && next <= 500000)
        if (sister(next)((time + 1) % 2) > time + 1) {
          q.push({next, time + 1});
          sister(next)((time + 1) % 2) = time + 1;
        }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> k;
  bfs();
  int step = 1;
  while (k < 500001) {
    if (sister(k)(brother(k) % 2) <= brother(k)) {
      cout << brother(k);
      return 0;
    }
    if (k + step < 500001)
      brother(k + step) = brother(k) + 1;
    k += step;
    step++;
  }
  cout << -1;
  return 0;
}