[1697] 숨바꼭질

• 입력: 수빈이 위치 N 수빈이 동생 위치 K 100,000이하의 자연수
• 출력: 수빈이가 동생을 찾기 위해 걸리는 최소 시간
• 조건: 수빈이는 현재 자리에서 한 칸 앞으로 가거나 뒤로 갈 수 있으며 두 배로 이동할 수 있다.
• 알고리즘: BFS
• 소스코드
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> #include <queue> using namespace std; #define MAX 100000 #define min(a, b) (a < b ? a : b) int main() { int n, k; scanf("%d%d", &n, &k); vector<int> step(MAX + 1, MAX + 1); step[n] = 0; queue<int> time; time.push(n); while (!time.empty()) { int here = time.front(); time.pop(); if (here == k) break; if (here + 1 <= MAX && step[here + 1] > step[here] + 1) { step[here + 1] = step[here] + 1; time.push(here + 1); } if (here - 1 >= 0 && step[here - 1] > step[here] + 1) { step[here - 1] = step[here] + 1; time.push(here - 1); } if (here * 2 <= MAX && step[here * 2] > step[here] + 1) { step[here * 2] = step[here] + 1; time.push(here * 2); } } printf("%d\n", step[k]); return 0; }
• 문제 참고: https://www.acmicpc.net/problem/1697