-
[BOJ / C++] 1697번 : 숨바꼭질Study (etc)/Problem Solving 2022. 7. 22. 22:45
문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
Solved.ac 레벨
실버 I
풀이
#include <bits/stdc++.h> #define MAX 100001 using namespace std; int n, k; //수빈이의 위치와 동생의 위치 queue< pair<int, int> > q; //수빈이가 이동할 위치와 이동할 때 걸린 시간 pair로 저장 bool visited[MAX]; //방문 void BFS(int n){ visited[n] = true; q.push(make_pair(n, 0)); //첫 시작점, 시간 0 while(!q.empty()){ int move = q.front().first; //이동 int time = q.front().second; //시간 q.pop(); if(move == k){ cout << time << '\n'; break; } int mov1 = move - 1; //X - 1 걷기 int mov2 = move + 1; //X + 1 걷기 int mov3 = move * 2; //X * 2 순간이동 if(mov1 >=0 && mov1 < MAX && visited[mov1] == false){ visited[mov1] = true; q.push(make_pair(mov1, time + 1)); } if(mov2 >=0 && mov2 < MAX && visited[mov2] == false){ visited[mov2] = true; q.push(make_pair(mov2, time + 1)); } if(mov3 >= 0 && mov3 < MAX && visited[mov3] == false){ visited[mov3] = true; q.push(make_pair(mov3, time + 1)); } } } int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> k; BFS(n); return 0; }
1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
'Study (etc) > Problem Solving' 카테고리의 다른 글
[BOJ / C++] 9205번 : 맥주 마시면서 걸어가기 (0) 2022.07.24 [BOJ / C++] 2468번 : 안전 영역 (0) 2022.07.24 [BOJ / C++] 2667번 : 단지번호붙이기 (0) 2022.07.21 [BOJ / C++] 2178번 : 미로 탐색 (0) 2022.07.21 [BOJ / C++] 2644번 : 촌수계산 (BFS) (0) 2022.07.15