백준 1697: 숨바꼭질/BFS

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

X가 3으로 나누어 떨어지면, 3으로 나눈다.

X가 2로 나누어 떨어지면, 2로 나눈다.

1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

---

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

---

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1

2

예제 출력 1

1

예제 입력 2

10

예제 출력 2

3

힌트

10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

---

해결 코드

#include <iostream>
#include <vector>
#include <queue>

#pragma warning(disable: 4996)

using namespace std;

bool isCheck[100010];

int main() {
    int N, K, t = 0, ans, x1, x2, x3;
    cin >> N >> K;

    queue<pair<int, int>> q;
    q.emplace(N, 0); // 현재 위치, 방문횟수

    while (!q.empty()) {
        N = q.front().first; // 현재 위치
        t = q.front().second; // 방문 횟수
        q.pop();

        if (N == K) {
            ans = t;
            break;
        }

        x1 = N - 1;
        x2 = N + 1;
        x3 = 2 * N;

        if (0 <= x1 && !isCheck[x1]) {
            isCheck[x1] = true;
            q.emplace(x1, t + 1);
        }

        if (K >= x2 && !isCheck[x2]) {
            isCheck[x2] = true;
            q.emplace(x2, t + 1);
        }

        if (K +1 >= x3 && !isCheck[x3]) {
            isCheck[x3] = true;
            q.emplace(x3, t + 1);
        }

    }

    cout << ans << endl;

    return 0;
}

boolean 형인 isCheck 배열을 만들어주어서 위치 별 중복 체크를 막는다.

큐가 빌 때까지 계속 반복해준다.

-1, +1, *2 순서로 큐에 넣어줘야한다.

사실 너무 오랜만에 코딩 알고리즘에 손을 대기도 했고, C++를 제대로 배운적이 없어서 유튜브와 사람들의 풀이를 보며 문제를 해결했다. 큐 문법은 이론만 알고, 또 C로만 구현해봐서 이렇게 사용해보는 것은 처음이다. 함수 사용하니까 정말 편하다 ㅎㅎ

암튼... 여러번 복습해야할 것 같다.