백준 1697번 숨바꼭질

문제 링크 : https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

풀이

bfs 문제입니다!

수빈이의 이동 방법이 3가지이고, n과 k의 범위가 0~10만 이기 때문에,

이 문제는 최대 10만 x 3 번만에 풀 수 있다.(사실 더 적게 걸릴 것이다.)

추가로, 이런 문제는 수빈이가 이동할 수 있는 범위가 10만이 아니라 10만 범위 밖으로 벗어난 후 뒤돌아 올 수도 있기 때문에 배열 범위 설정은 보통 범위 * 2 만큼 해주는게 적당하다.

 

그럼 bfs를 구현해보자. 수빈이의 지점 N에서 칠 수 있는 가지는 다음과 같이 3가지이다

• N+1
• N-1
• 2N

수빈이의 위치마다 이 가지들을 치면서 동시에 시간을 +1씩 해주면,

K지점에 도달할 때의 시간이 답이 된다.

 

소스 코드

#define MAX 200001
#include <iostream>
#include <queue>
using namespace std;
 
bool check[MAX];
int main()
{
    int n, k; scanf("%d%d", &n, &k);
    int pos = 0; int cnt = 0;
    queue<pair<int, int> >q;
    q.push(make_pair(n, 0));
    while (!q.empty()) {
        pos = q.front().first;
        cnt = q.front().second;
        check[pos] = true;
        q.pop();
 
        if (check[k] == true) break;
 
        if (pos + 1 < MAX && check[pos + 1] == false) {
            q.push(make_pair(pos + 1, cnt + 1));
        }
        if (pos - 1 >= 0 && check[pos - 1] == false) {
            q.push(make_pair(pos - 1, cnt + 1));
        }
        if (pos * 2 < MAX && check[pos * 2] == false) {
            q.push(make_pair(pos * 2, cnt + 1));
        }
    }
    printf("%d", cnt);
    return 0;
}

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~