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

1697번: 숨바꼭질

 

문제

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

1697번: 숨바꼭질

 

 

풀이

BFS로 현재 위치로부터 +1, -1, ×2인 위치를 탐색한다. 만약 범위를 만족하면서 아직 방문하지 않았다면 큐에 추가해 주며 반복한다. visited 배열을 +1씩 해가며 몇 번만에 도달하는지 확인을 했다.

 

visited[k] 값을 출력하면 된다.

 

 

코드

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

int n, k;
vector<int> visited(100001, 0);

void bfs(int start) {
  queue<int> q;
  q.push(start);
  if (start == k)
    return;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    if (x + 1 >= 0 && x + 1 <= 100000)
      if (!visited[x + 1]) {
        q.push(x + 1);
        visited[x + 1] = visited[x] + 1;
      }
    if (x - 1 >= 0 && x - 1 <= 100000)
      if (!visited[x - 1]) {
        q.push(x - 1);
        visited[x - 1] = visited[x] + 1;
      }
    if (x * 2 >= 0 && x * 2 <= 100000)
      if (!visited[x * 2]) {
        q.push(x * 2);
        visited[x * 2] = visited[x] + 1;
      }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> k;
  bfs(n);
  cout << visited[k] << '\n';
  return 0;
}