[백준] 1697번. 숨바꼭질
[백준] 1697번. 숨바꼭질
1. 문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
2. 입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
3. 출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
4. 풀이
BFS
로 풀었다.- 이미 갔던 곳이 아닌 모든 곳의 경우의 수를 구했다.
BFS
라 최단거리가 보장된다.
5. 처음 코드와 달라진 점
- 범위 설정에서 등호를 빼먹어서 틀렸다. 후...
6. 코드
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int arr[100001] = { 0, };
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int start, target;
cin >> start >> target;
queue<int> q;
if (start != target) q.push(start);
while (!q.empty()){
int x = q.front();
if (x == target) break;
q.front();
q.pop();
int nx1 = x + 1;
int nx2 = x - 1;
int nx3 = x * 2;
if (nx1 <= 100000 && arr[nx1] == 0) {
q.push(nx1);
arr[nx1] = arr[x] + 1;
}
if (nx2 >= 0 && arr[nx2] == 0) {
q.push(nx2);
arr[nx2] = arr[x] + 1;
}
if (nx3 <= 100000 && arr[nx3] == 0) {
q.push(nx3);
arr[nx3] = arr[x] + 1;
}
}
cout << arr[target];
}
Author And Source
이 문제에 관하여([백준] 1697번. 숨바꼭질), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@e7838752/boj1697저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)