백준 - 숨바꼭질 : 1697번

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

1697번: 숨바꼭질

BFS를 사용해서 쉽게풀수 있는 문제다.

BFS는 아래그림과 같이 그래프 순회방법중의 하나이다.

특히, BFS는 간선의 가중치가 모두 동일한 경우, 최단거리와 같은 최소비용 문제를 해결하기에 적합합니다.

 

아래 그래는 Graph의 표현 방법과 순회에 대해서 대략적으로 요약한 것이니 참고하시기 바랍니다.

인접리스트의 경우 실제 리스트를 사용하기 보다는 보통 vector를 사용해서 해결하는 경우 많으니 참고하세요.

 

 

아래 BFS의 슈도코드라고 할까요? 대략적인 알고리즘을 확인 하실수 있겠습니다.

 

자~!! 이제 본 숨바꼭질 문제의 풀이 방법입니다. 아래 그림을 통해 찬찬히 고민해보시기 바랍니다.

수빈이의 위치 X에서 1초후에 이동할 수 있는 곳은 X-1, X+1, X*2 입니다. 어떤 이동방법을 선택하더라도 1초가 걸리니까, 이것은 모든 간선의 가중치가 1초라고 보면 되겠네요.^^

 

그리고X-1을 할때는 X-1이 0보다 작으면 중단하면 되겠죠.

X+1, X*2의 경우는 다음 위치가 200,000보다 작거나 같은때만 처리해주면 되겠네요.^^

 

 

많은 도움되셨길바라며, 아래 소스코드 참고하세요.^^

 

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,k,c[200005]={0,},v[200005]={0,},t;
    queue <int> q;
    scanf("%d %d",&n,&k);
    v[n]=1;
    c[n]=0;
    q.push(n);
    while(!q.empty())
    {
        t=q.front();
        q.pop();
        if(t-1 >= 0 && v[t-1]==0){
            q.push(t-1);
            c[t-1]=c[t]+1;
            v[t-1] = 1;
        }
        if(t+1 < 200000 && v[t+1]==0){
            q.push(t+1);
            c[t+1]=c[t]+1;
            v[t+1] = 1;
        }
         if(t*2 < 200000 && v[t*2]==0){
            q.push(t*2);
            c[t*2]=c[t]+1;
             v[t*2]=1;
        }
        //v[t-1]=v[t+1]=v[t*2]=1;
    }
    printf("%d",c[k]);
    return 0;
}