백준 17071번 숨바꼭질 5 ( C++ )

문제

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

 

해설

+1 -1을 통해 2*n번째 전 자리에 돌아갈 수 있다는것이 핵심인 문제

이를 통해 짝수번째에 갔던 자리 or 홀수번째에 갔던 자리는 각각 짝수/홀수일때 다시 갈 수 있는것이 핵심

코드

// 플러드필
#include <bits/stdc++.h>
using namespace std;
 
int n, k, timeNow;
int ret = -1;
int visited[2][500004];
 
void bfs(int start)
{
  queue<int> q;
  q.push(start);
  visited[timeNow % 2][start] = 1;
 
  while (q.size())
  {
    k += timeNow;
    if (k > 500000)
    {
      ret = -1;
      return;
    }
 
    if (visited[timeNow % 2][k] == 1)
    {
      ret = timeNow;
      return;
    }
 
    int qSize = q.size();
    timeNow++;
    for (int i = 0; i < qSize; i++)
    {
      int location = q.front();
      q.pop();
 
      for (int next : {location + 1, location - 1, location * 2})
      {
        int tmpTime = (timeNow) % 2;
        if (next >= 0 && next <= 500000 && visited[tmpTime][next] == 0)
        {
          visited[tmpTime][next] = 1;
          q.push(next);
        }
      }
    }
  }
}
 
int main()
{
  cin >> n >> k;
 
  bfs(n);
  cout << ret;
}