[백준/C++]1697, 13913, 13549번_ 숨바꼭질, 숨바꼭질 4, 숨바꼭질 3

비슷한 유형의 문제들을 한번에 정리해보겠습니다.
첫 번째 문제는 다음과 같습니다.

제 풀이는 다음과 같습니다.

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int a[100001]={0, }; int ch[100001]={0, };
  int n, k, dis, w; queue<pair<int, int>> q;
  cin>>n>>k;
  ch[n]=1; q.push({n, 0});

  while(!q.empty()){
    pair<int, int> p = q.front(); q.pop();
    dis = p.second; w = p.first;
    if(p.first == k) break;

    if(2*w<=100000 && ch[2*w]==0){
      ch[2*w]=1; q.push({2*w, dis+1});
    }
    if(w-1>=0 && ch[w-1]==0){
      ch[w-1]=1; q.push({w-1, dis+1});
    }
    if(w+1<=100000 && ch[w+1]==0){
      ch[w+1]=1; q.push({w+1, dis+1});
    }
  }

  cout<<dis;
  return 0;
}

---

두 번째 문제는 다음과 같습니다.

이 문제가 세 문제중 그래도 살펴볼만한 지점이 있어서 짚고 넘어가겠습니다.
저는 이전의 이동 위치를 배열에 담아두어서 이를 기록하였습니다.
ex) res[다음위치] = 현재위치

예전에 dp문제중 최대부분증가수열에서 이와 비슷한 유형이 있었는데요,
그 문제에서도 부분수열을 출력하는 게 있었는데 그 때에 이렇게 저장했던 방법을 그대로 이용하였습니다.

풀이는 다음과 같습니다.

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int a[100001]={0, }; int ch[100001]={0, };
  int res[100001]={0, };
  int n, k, dis, w; queue<pair<int, int>> q;
  cin>>n>>k;
  ch[n]=1; res[n]=-1; q.push({n, 0});

  while(!q.empty()){
    pair<int, int> p = q.front(); q.pop();
    dis = p.second; w = p.first;
    if(p.first == k) break;

    if(2*w<=100000 && ch[2*w]==0){
      ch[2*w]=1; res[2*w]=w; q.push({2*w, dis+1});
    }
    if(w-1>=0 && ch[w-1]==0){
      ch[w-1]=1; res[w-1]=w; q.push({w-1, dis+1});
    }
    if(w+1<=100000 && ch[w+1]==0){
      ch[w+1]=1; res[w+1]=w; q.push({w+1, dis+1});
    }
  }

  cout<<dis<<endl;
  vector<int> v;
  while(1){
    v.emplace_back(w);
    w = res[w];
    if(w==-1) break;
  }
  for(int i=v.size()-1; i>=0; i--) cout<<v[i]<<" "; // 역추적
  return 0;
}

---

세 번째 문제는 다음과 같습니다.

풀이는 다음과 같습니다.

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int a[100001]={0, }; int ch[100001]={0, };
  int n, k, dis, w; queue<pair<int, int>> q;
  cin>>n>>k;
  ch[n]=1; q.push({n, 0});

  while(!q.empty()){
    pair<int, int> p = q.front(); q.pop();
    dis = p.second; w = p.first;
    if(p.first == k) break;

    if(2*w<=100000 && ch[2*w]==0){
      ch[2*w]=1; q.push({2*w, dis});
    }
    if(w-1>=0 && ch[w-1]==0){
      ch[w-1]=1; q.push({w-1, dis+1});
    }
    if(w+1<=100000 && ch[w+1]==0){
      ch[w+1]=1; q.push({w+1, dis+1});
    }
  }

  cout<<dis;
  return 0;
}