[백준] 1697번 숨바꼭질 C++ 풀이

---

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• BFS

---

문제 설명

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

---

입력 설명

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

---

출력 설명

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

---

예제 입력

5 17

---

예제 출력

4

---

아이디어

수빈이가 1초 동안 움직일 수 있는 경우의 수는 x-1, x+1, 2*x 이렇게 셋이다.

BFS를 사용하면 3가지 경우의 수를 모두 탐색하며 동생을 찾는 최소 시간을 구할 수 있다.

---

알고리즘

(현재 내 위치, 걸린 시간)을 pair로 묶어서 q에 넣는다.

입력받은 수빈이의 위치를 q에 넣어주고 동생을 찾을 때까지 BFS를 돌린다.

동생을 찾았다면 그때까지 걸린 시간을 출력한다.

---

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> visit(100001, 0);
queue<pair<int,int>> q;
int BFS(int b)
    {
        int cnt=0;
        while(!q.empty())
            {
                int x = q.front().first;
                cnt = q.front().second;
                q.pop();
                if(x == b) break;
                if(0 <=x && x<=100000 )
                {
                    if(0 <= x+1 && x+1 <= 100000 && visit[x+1] == 0)
                    {
                        visit[x+1] = 1;
                        q.push(make_pair(x+1,cnt+1));
                    }
                    if(0 <= x-1 && x-1 <= 100000 && visit[x-1] == 0)
                    {
                        visit[x-1] = 1;
                        q.push(make_pair(x-1,cnt+1));
                    }
                    if(0 <= 2*x && 2*x <= 100000 && visit[2*x] == 0)
                    {
                        visit[2*x] = 1;
                        q.push(make_pair(2*x,cnt+1));
                    }
                }
            }
        return cnt;
    }
int main() {
    int a,b;
    cin>>a>>b;
    q.push({a,0});
    visit[a] = 1;
    cout << BFS(b);
    return 0;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/1697

최근에 BFS를 사용하는 문제를 여러 번 풀어서 한 번에 정답을 맞힐 수 있었다.

다른 실버1 난이도의 문제들보다는 쉽게 느껴졌다.

 

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!