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번 조건문에 걸릴시 당연하게 최솟값이 나오게 되는 것이다... 반복문에 익숙하지않다보니 생긴 착각이였다!