백준 1697번 숨바꼭질

🔒[문제 url]

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

🪄전체 코드

#include <iostream>
#include <queue>
using namespace std;

const int MAX = 100'000;

int n, k;
bool visited[100'001];
queue<pair<int, int>> q;//<좌표, 초>

void INPUT()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k;
}

int BFS()
{
	q.push({n,0});//수빈이의 처음 위치는 n이고 걸린 시간은 0
	visited[n] = true;

	while (!q.empty())
	{
		int now = q.front().first;//현재 위치
		int second = q.front().second;//현재 위치까지 걸린 시간
        q.pop();
        
        //동생 찾으면 걸린 시간 반환
		if (now == k) return second;
        
		if (now + 1 <= MAX && !visited[now + 1])
		{//x+1로 이동
			q.push(make_pair(now + 1, second + 1));
			visited[now + 1] = true;
		}
		if (now - 1 >= 0 && !visited[now - 1])
		{//x-1로 이동
			q.push(make_pair(now - 1, second + 1));
			visited[now - 1] = true;
		}
		if (now * 2 <= MAX && !visited[now  * 2])
		{//2*x로 이동
			q.push(make_pair(now * 2, second + 1));
			visited[now * 2] = true;
		}
	}
}

void solve()
{
	cout << BFS();
}

int main()
{
	INPUT();
	solve();
}

🥇문제 후기

GOLD5 미만 난이도는 알고리즘 및 풀이 설명을 주석으로 대체합니다.
주석을 참고해주세요.