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

17071번: 숨바꼭질 5

 

문제

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

17071번: 숨바꼭질 5

 

 

풀이

수빈이(편의상 누나)는 다른 숨바꼭질 문제들처럼 +1, -1, ×2로 이동 가능하고 시간은 1초 걸린다. 대신 동생이 1초에 1칸, 2초에 2칸,... N초에 N칸씩 움직인다. 따라서 BFS 알고리즘을 사용해서 풀 수 있다.

 

처음 접근 방식은 각각에 대해 BFS를 하며 (동생은 사실 하나만 이동하지만) 시간 단위로 이동하고, 이동할 때마다 동생의 위치에 누나가 도달할 수 있는지 확인했다. 그러나 71%에서 TLE를 받았다. 해결하려고 질문 게시판을 찾아봤고... 정말 대단한 규칙과 아이디어를 발견했다.

 

바로 누나가 지나갔던 곳을 또 지나갈 수 있다는 것이다. 사실 이건 생각을 했었고 위에 구현할 때도 적용을 어찌어찌 하긴 했었다. 근데 왔다 갔다를 무한 반복하게 되면 시간이 홀수일 때 도착했다면 이후 홀수인 시간엔 항상 방문이 가능하고, 짝수일 때도 마찬가지란 것이다. 따라서 이걸 홀수 시간일 때 처음 도착한 시간, 짝수 시간일 때 처음 도착한 시간을 따로 기록하는 것이다.

 

따라서 2차원 배열을 [위치][홀/짝]으로 만들어준다. 위치와 시간을 pair로 큐에 넣어 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;
}