[백준] 1697 숨바꼭질 BFS

문제 :

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

분석 :

풀지 못했던 문제를 풀었다 🤭 처음엔 재귀로 접근하다 가까운 거리먼저 탐색 해야 한다는 것을 깨달았다. 

최단 거리를 찾는 bfs 문제이므로 queue를 사용했고 수빈이의 움직임 moving 배열에 넣은 뒤 visit에 움직인 거리만큼을 +1 해줘서 누적시켰다.

그리고 k에 도달했을 때 누적된 값을 출력시키면 끝!!

 

 

c++ 코드 :

//
//  1697_hide_seek.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/02/21.
//

#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>


using namespace std;
#define MAX 100000
int visit[MAX + 1];
int n, k;
int moving[3] = { - 1, 1, 2}; //walk, jump

void hide_and_seek_bfs(int num){
    queue<int> q;
    q.push(num);
    visit[num] = 0;
    
    if(num == k){
        cout << 0 << '\n';
    }
    
    while(!q.empty()){
        int temp = q.front();
        int next;
        q.pop();
        
        for(int i = 0; i < 3; i++){
            if(i == 2) next = moving[i] * temp;
            else next = moving[i] + temp;
            
            //예외 처리
            if(next < 0 || next > 100000) continue;
            if(visit[next] != -1) continue;
            
            q.push(next);
            visit[next] = visit[temp] + 1;
            
            if(next == k){
                cout << visit[next] << '\n';
                break;
            }
            
            
        }
    }
}



int main(){
    memset(visit, -1, sizeof(visit));
    cin >> n >> k;
    hide_and_seek_bfs(n);
    return 0;
}