[백준] 1697번 숨바꼭질

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define MAX 100001
typedef long long ll;
using namespace std;

//BFS 계산
int N,K;
int visited[MAX] ={}; //정점 방문, 걸린 시간 저장

int bfs(){
    queue<int> q; //현재 위치에서 이동 가능한 다음 위치 저장
    q.push(N); //시작 위치
    visited[N]=0;
    while(!q.empty()){
        int nowPosition = q.front();
        q.pop();
        
        if(nowPosition == K) break;
        
        int minusPosition = nowPosition-1;
        int plusPosition = nowPosition+1;
        int multiPosition = nowPosition*2;
        
        if(minusPosition >=0 && visited[minusPosition] ==0){ //방문하지 않았으면
            q.push(minusPosition);
            visited[minusPosition] = visited[nowPosition] +1; //방문 시간 기록
        }
        if(plusPosition < MAX && visited[plusPosition]==0){
            q.push(plusPosition);
            visited[plusPosition] = visited[nowPosition] +1;
        }
        if(multiPosition < MAX && visited[multiPosition] ==0){
            q.push(multiPosition);
            visited[multiPosition] = visited[nowPosition] +1;
        }
    }
    return visited[K];
}

int main(){
    cin>>N>>K;
    cout<<bfs();
    return 0;
}

<풀이>

+1, -1, *2를 모두 탐색하는 BFS 알고리즘이다.

Q. N=5, K=17이라고 하자

N=5에서 시작; 이동 가능한 위치: 4,6,10 -> 방문하지 않았으므로 큐[4, 6, 10] ;

visited[4]=visited[5]+1=1, visited[6]=1, visited[10]=1

N=4로 이동; 이동 가능한 위치: 3,5,8 -> 큐[6, 10, 3, 8] ; visited[3]=visited[4]+1=2, visited[8]=2

N=6로 이동; 이동 가능한 위치: 5,7,12 -> 큐[10, 3, 8, 7, 12]; visited[7]=visited[6]+1=2, visited[12]=visited[6]+1=2

반복해서 visited[K=17]에 도달하면 종료함, 그때의 값이 최소시간임

 

<참고 사이트>

https://animoto1.tistory.com/entry/%EB%B0%B1%EC%A4%80-1697-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88-C