백준 1697 숨바꼭질 c++ [컴공과고씨]

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

1697번: 숨바꼭질

이 문제 같은 경우 처음에는 계산 형식으로 고민을 하다 bfs를 써야겠다는 생각이 들었다.

bfs를 쓰니 간단히 해결이 되었다. bfs 구성은 동생을 찾지 못하면 x+1, x-1, 2x를 visit에 넣어 방문했는지 검사한 후 방문을 하지 않았다면 각각을 q에 넣어주면 간단히 해결된다.

 

전체코드

#include <iostream>
#include <queue>
using namespace std;
int n, k;
bool visit[100001];
void bfs(int a){
    queue<pair<int, int>> q;
    q.push(make_pair(a, 0));
    while(!q.empty()){
        int x = q.front().first;
        int cnt = q.front().second;
        q.pop();
        if(x==k){
            cout << cnt;
            break;
        }
        if(x+1 >=0 && x+1<100001){
            if(!visit[x+1] ){
                visit[x + 1] = true;
                q.push(make_pair(x + 1, cnt + 1));
            }
        }
        if(x-1 >=0 && x-1<100001){
            if(!visit[x-1]){
                visit[x - 1] = true;
                q.push(make_pair(x - 1, cnt + 1));
            }
        }
        if(2*x >=0 && 2*x<100001){
            if(!visit[2*x]){
                visit[2*x] = true;
                q.push(make_pair(2 * x, cnt + 1));
            }
        } // 각 다음 좌표마다 q에 넣어준다.
    }
}
int main(){
    cin >> n >> k;
    visit[n] = true;
    bfs(n);
    return 0;
}

사용 문법 : bfs

 

yea!