BOJ 1697 숨바꼭질 BFS

- BFS

- 큐 이용

- for문 + dx 좌표 잡는 대신, 가능한 3번의 경우를 모두 큐에 넣어버림

 

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

 

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

int visited[100000]={0};
int t[100000]={0}; // 시간 측정

int main(){
  int st, en;
  int cnt=0;
  scanf("%d %d", &st, &en);
  visited[st]=1; // 현재 위치를 1로

// BFS
  queue<int> q;
  q.push(st);
  visited[st]=1;

  while(!q.empty()){
    int cur = q.front();
    q.pop();

// 3방향
    // cur - 1
    int ncur = cur - 1;
    if(ncur>=0 && ncur<=100000){
      if(visited[ncur]==0){
        visited[ncur]=1;
        q.push(ncur);
        t[ncur] = t[cur] + 1;
      }
    }

    // cur + 1
    ncur = cur + 1;
    if(ncur>=0 && ncur<=100000){
      if(visited[ncur]==0){
        visited[ncur]=1;
        q.push(ncur);
        t[ncur] = t[cur] + 1;
      }
    }

    // cur * 2
    ncur = cur * 2;
    if(ncur>=0 && ncur<=100000){
      if(visited[ncur]==0){
        visited[ncur]=1;
        q.push(ncur);
        t[ncur] = t[cur] + 1;
      }
    }
  }  /// while end
  printf("%d", t[en]);
}