2024 - 09- 23 C++ 코딩테스트 10주완성 D+39
백준 17071 문제 - 숨바꼭질 5
수빈이는 동생과 숨바꼭질을 하고 있다.
수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다.
수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다.
순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
동생은 항상 걷기만 한다. 동생은 항상 매 초마다 이동을 하며, 이동은 가속이 붙는다.
동생이 이동하는 거리는 이전에 이동한 거리보다 1을 더한 만큼 이동한다.
즉, 동생의 처음 위치는 K, 1초가 지난 후 위치는 K+1, 2초가 지난 후 위치는 K+1+2, 3초가 지난 후의 위치는 K+1+2+3이다.
수빈이와 동생의 위치가 주어졌을 때,
수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
(동생을 찾는 위치는 정수 좌표이어야 하고, 수빈이가 0보다 작은 좌표로, 50만보다 큰 좌표로 이동하는 것은 불가능하다.)
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
수빈이가 동생을 찾을 수 없거나, 찾는 위치가 500,000을 넘는 경우에는 -1을 출력한다.
실습코드
#include <bits/stdc++.h>
using namespace std;
const int max_n = 500000;
int visited[2][max_n + 4], a, b, ok, turn = 1;
int main() {
cin >> a >> b;
if(a == b){cout << 0 << "\n"; return 0;}
queue<int> q;
visited[0][a] = 1;
q.push(a);
while(q.size()){
b += turn;
if(b > max_n)break;
if(visited[turn % 2][b]) {
ok = true;
break;
}
int qSize = q.size();
//q.size 만큼 반복문
for(int i = 0; i < qSize; i++){
//q.front()부터 시작해서 끝까지
int x = q.front(); q.pop();
//x+1,x-1,x*2 만큼 반복문
for(int nx : {x + 1, x - 1, x * 2}){
//만약 nx가 음수거나 max_n 값을 넘거나 visited 값이 있을시 넘어감
if(nx < 0 || nx > max_n || visited[turn % 2][nx]) continue;
//다음 turn 수는 현재 도는 turn 보다 +1 많으므로 홀수일때는 짝수 짝수일때는 홀수로
//현재 visited 의 값에다가 +1 하여준다.
visited[turn % 2][nx] = visited[(turn + 1) % 2][x] + 1;
if(nx == b){
ok = 1; break;
}
q.push(nx);
}
if(ok)break;
}
if(ok)break;
turn++;
}
if(ok) cout << turn << "\n";
else cout << -1 << "\n";
return 0;
}
이 문제에서 핵심 알고리즘은 동생의 위치인 b가 turn 초를 누적해서 더한 값으로 계속 이동한다는 것이다.
이를 반복문으로 표현하면 turn 의 값을 반복문이 돌 동안 계속 증감해주어 b에 더해주면 된다. ( b += turn )
로직은 두가지이다.
1. 수빈이의 위치를 x+1,x-1,2*x로 bfs 탐색 알고리즘을 돌려서 더해준 다음 b의 값이 나오면 turn 의 값을 출력해주거나
2. 수빈이가 먼저 그 위치를 도착했을 경우의 초 a와 동생이 그 위치를 도착했을 때 초 b 의 값이 둘다 홀수 또는 짝수일시
수빈이가 +1,-1 로 왔다갔다하면서 동생의 위치로 올 수 있으므로 visited[turn % 2][동생위치] 가 성립할 경우 turn 의 값을
출력시켜주면 된다.
2번 로직을 하루종일 생각해도 이해가 안되는 부분이 어떻게 최솟값을 내놓을까 라는 의문이 있었는데,
생각해보니까 while(q.size()) 문안에서 turn++ 한후 계속 검사를 하여주니 2번 조건문에 걸릴시 당연하게 최솟값이 나오게 되는 것이다... 반복문에 익숙하지않다보니 생긴 착각이였다!