백준#1697 숨바꼭질

 

난이도 : 실버1
소요시간 :  1시간 28분
사용한 풀이법 : dfs,queue

---

풀이 과정

1. 수빈 현 위치로 부터의 거리 측정용 배열 dist[], 이동 가능 위치 체크용 큐 Q[] 생성;
2. dist[]는 -1로 초기화, Q[]에 수빈 현위치 push;
3. dist[k]에 값이 들어가기 전까지 while 루프{}
4. 현위치 확인용 변수 cur에 Q.front() 대입;
5. cur이 -1, +1,*2 일때의 상황 for문 돌리면서 bfs 진행
6. 조건 충족 시, 해당 상황의 dist 값을 dist[cur]+1로 설정;
7. while 탈출 시 dist[k]값 출력;

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

queue<int> Q;
int dist[100002];

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

    int n,k;
    cin >> n >> k;
    
    fill(dist,dist+100001,-1);
    dist[n]=0;
    Q.push(n);
    
    while(dist[k]==-1){
        int cur = Q.front();
        Q.pop();
        for(int i=0; i<3; i++){
            int pos = (i == 0)?cur-1 : (i ==1)?cur+1 : cur*2;
            if(pos<0 || pos>100000) continue;
            if(dist[pos]!=-1) continue;
            dist[pos] = dist[cur]+1;
            Q.push(pos);
        }
    }
    cout << dist[k] << '\n';
}