[BOJ] 1697 숨바꼭질

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

1697번: 숨바꼭질

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

BFS

 

---------------------------------------------------풀이----------------------------------------------------

 

N에서 시작해 +1, -1, *2 한 위치를 이동한 수만큼과 함께 큐에 삽입한다.

queue의 front에 있는 위치가 K일 경우 종료한다.

또한, 중복을 방지하기 위해 visited[] 배열을 만들었다.

특정 위치에 이미 방문했으면, 그 순간이 최소인 케이스이므로 다시 방문하지 않도록 한다.

X+1과 X-1이 0이상이고 방문하지 않았으면 큐에 삽입한다.

또한, K의 두배보다 커지면 잘못된 방향(멀어지는 방향)으로 이동하는 것이므로 최선이 아니게 된다.

따라서, X*2가 K의 두배 이하이면서 방문하지 않은 경우 큐에 삽입한다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>
#include <map>

using namespace std;

// X+1 or X-1 or X*2로 이동
int main(void){
    FASTIO;
    int N, K;
    cin >> N >> K;

    bool visited[300'000] = {false, };

    // bfs
    queue<pair<int,int> > q;
    // 현재 위치, 이동한 만큼
    pair<int,int> cur;
    cur.first = N;
    cur.second = 0;
    q.push(cur);
    while(!q.empty()){
        cur = q.front();
        q.pop();
        visited[cur.first] = true;
        if(cur.first == K){
            break;
        }
        if(cur.first+1>=0 && !visited[cur.first+1]) q.push(make_pair(cur.first+1, cur.second+1));
        if(cur.first-1>=0 && !visited[cur.first-1]) q.push(make_pair(cur.first-1, cur.second+1));
        if(cur.first*2 <= K*2 && !visited[cur.first*2]) q.push(make_pair(cur.first*2, cur.second+1));
    }

    cout << cur.second << "\n";

    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

bfs를 이용한 최단거리 탐색 문제와 유사하다.

bfs로 우선순위 큐가 아닌 일반 큐를 사용해도, depth 별로 탐색하기때문에

맨 처음 발견된 target이 정답임을 알 수 있다.