(ALGO) 백준 1697번 문제 - 숨바꼭질

04 Jul 2017

Reading time ~1 minute

간단한 BFS 가지치기 문제.
100001개의 배열을 사용하고 이미 방문한 노드는 다시 방문하지 않기 때문에,
100001번 보다 적은 연산을 하게된다.

구현 소스

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    int N, K;
    bool visit[100001] = {0,};

    cin>>N>>K;

    queue<pair<int,int>> q;

    q.push(pair<int, int>(N,0));

    while(!q.empty())
    {
        int pos = q.front().first;
        int depth = q.front().second;

        if(pos == K)
            break;

        q.pop();

        visit[pos] = true;

        if(pos-1 >= 0 && !visit[pos-1])
            q.push(pair<int,int>(pos-1, depth+1));
        if(pos+1 <= 100000 && !visit[pos+1])
            q.push(pair<int,int>(pos+1, depth+1));
        if(pos*2 <= 100000 && !visit[pos*2])
            q.push(pair<int,int>(pos*2, depth+1));

    }

    cout<<q.front().second<<endl;

    return 0;
}

– 출처
https://www.acmicpc.net/problem/1697