[백준/c++] 1697번: 숨바꼭질

 

 

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

문제 요약

 

수빈이가 이동할 수 있는 경로 X-1, X+1, X*2

동생을 찾을 수 있는 가장 빠른 시간은 몇 초인가?

 

범위

 

수빈이의 위치 N(0 ≤ N ≤ 100,000)

동생의 위치 K(0 ≤ K ≤ 100,000)

 

 

 

---

 

 

수빈이가 이동할 수 있는 경로는 3가지이다.

 

- x-1

- x+1

- x*2

 

동생을 찾을 수 있는 가장 빠른 시간을 찾아야 한다. 위의 3가지 경로는 한 번 이동할 때 1초씩 걸리므로 수빈이의 위치에서 동생의 위치까지의 최소 이동 횟수를 구하면 된다.

 

최소 이동 횟수는? 최단 거리 → BFS

 

이동할 수 있는 경로가 상하좌우나 대각선으로 주어진 것이 아니라 조금 특이하게 주어졌으므로 배열에 넣어서 해당 경로의 형태를 갖추도록 했다. 3가지 경로를 돌면서 수빈이와 동생이 이동할 수 있는 경로(0 ≤ N, K ≤ 100,000)를 이탈한 경우 다음 위치로 넘어가도록 했다.

그리고 만약 방문한 곳이 아니라면 +1 (이동=1초) 큐에 넣어주면서 BFS를 진행했다.

 

 

 

💡 여기서 거리(초)를 저장하는 배열 dist의 초기값을 -1로 한 이유는?

 

예제를 보면 수빈이의 위치 5 동생의 위치 17이다.→ 5 - 10 - 9 - 18 - 17으로 이동하는 것이 가장 빠른데, 만약 초기값을 0으로 했으면 5부터 +1이 되어 오답이 나오게 된다.맨 앞 원소에 대해서도 값을 추가하고 싶다면 초기값을 0으로 해줘야 한다.

 

 

#include <iostream>
#include <queue>
using namespace std;
int n, k, dist[100002];

void input(){
    cin >> n >> k;
}

void BFS(){
    for(int i=0; i<=100000; i++) dist[i] = -1;
    queue<int> q;
    q.push(n);
    dist[n] = 0;
    while(!q.empty()){
        int x = q.front(); q.pop();
        int ds[3] = {x-1, x+1, 2*x}; //이동가능한 경로
        for(int i=0; i<3; i++){
            if(ds[i] < 0 || ds[i] > 100000) continue;   //경로 이탈 -> 패스
            if(dist[ds[i]] == -1){                      //방문했던 곳이 아니라면
                dist[ds[i]] = dist[x]+1;
                q.push(ds[i]);
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    BFS();
    cout << dist[k] << '\n';
    return 0;
}

 

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!