[백준] 12761번. 돌다리

링크텍스트

1. 문제

동규와 주미는 일직선 상의 돌 다리 위에있다. 돌의 번호는 0 부터 100,000 까지 존재하고 동규는 N번 돌 위에, 주미는 M번 돌 위에 위치하고 있다. 동규는 주미가 너무 보고싶기 때문에 최대한 빨리 주미에게 가기 위해 A, B만큼의 힘을 가진 스카이 콩콩을 가져왔다. 동규가 정한 다리를 건너는 규칙은 턴 방식인데, 한 턴에 이동할 수 있는 거리는 이러하다. 현 위치에서 +1칸, -1칸을 이동할 수 있고, 스카이 콩콩을 이용해 현 위치에서 A나 B만큼 좌우로 점프할 수 있으며, 순간적으로 힘을 모아 현 위치의 A배나 B배의 위치로 이동을 할 수 있다. 예를 들어 지금 동규가 7번 돌 위에 있고 스카이 콩콩의 힘이 8이면 그냥 점프를 해서 15번 돌에 갈 수도 있고, 순간적으로 힘을 모아 56번 돌에 갈 수도 있다는 것이다. 주어진 8가지의 방법 중 적절한 방법을 골라서 최대한 빨리 동규가 주미를 만날 수 있게 도와주자. 단, 이동 과정에서 100,000보다 크거나 0보다 작은 번호의 돌은 존재하지 않으므로 갈 수 없고, 같은 방법을 계속 사용해도 되며 항상 도달할 수 있는 케이스만 주어진다.

2. 입력

입력의 첫 줄에 스카이 콩콩의 힘 A와 B, 그리고 동규의 현재위치 N, 주미의 현재 위치 M이 주어진다. (단, 2 ≤ A, B ≤ 30 이고 0 ≤ N, M ≤ 100,000)

3. 출력

동규가 주미에게 도달하기 위한 최소한의 이동 횟수를 출력하라.

4. 풀이

• BFS로 풀었다.
• 현재 위치에서
  - +1, -1, +A, -A, +B, -B, A, B를 한 결과를 각각 만든다.
• 8가지 이동 경우가 범위 안이고 아직 방문한 적 없다면, 전 단계까지 이동거리 +1해서 해당하는 배열의 인덱스에 저장한다.
• 위의 동작을 현재 위치와 목표 위치가 같을 때까지 반복한다.
  메모리 초과나지 않을까 걱정했는데 안났다.

5. 맘에 안드는 점

• 너무 하드 코딩 같아서 마음에 안든다.
• 배열을 이용해서 해볼까 고민도 했는데 그냥 일단 했다.

6. 코드

#include <iostream>
#include <queue>

using namespace std;

int arr[100001];

int main(void) {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    int powerA, powerB, start_position, target_position;
    cin >> powerA >> powerB >> start_position >> target_position;
 
    queue<int> q;
    q.push(start_position);

    while (!q.empty()) {
        int current_position = q.front();
        q.pop();

        if (current_position == target_position) break;

        int new_position = current_position + 1;
        if (new_position >= 0 && new_position <= 100000 && arr[new_position] == 0) {
            q.push(new_position);
            arr[new_position] = arr[current_position] + 1;
        }
        
        new_position = current_position - 1;
        if (new_position >= 0 && new_position <= 100000 && arr[new_position] == 0) {
            q.push(new_position);
            arr[new_position] = arr[current_position] + 1;
        }
        new_position = current_position + powerA;
        if (new_position >= 0 && new_position <= 100000 && arr[new_position] == 0) {
            q.push(new_position);
            arr[new_position] = arr[current_position] + 1;
        }
        new_position = current_position - powerA;
        if (new_position >= 0 && new_position <= 100000 && arr[new_position] == 0) {
            q.push(new_position);
            arr[new_position] = arr[current_position] + 1;
        }
        new_position = current_position + powerB;
        if (new_position >= 0 && new_position <= 100000 && arr[new_position] == 0) {
            q.push(new_position);
            arr[new_position] = arr[current_position] + 1;
        }
        new_position = current_position - powerB;
        if (new_position >= 0 && new_position <= 100000 && arr[new_position] == 0) {
            q.push(new_position);
            arr[new_position] = arr[current_position] + 1;
        }
        new_position = current_position * powerA;
        if (new_position >= 0 && new_position <= 100000 && arr[new_position] == 0) {
            q.push(new_position);
            arr[new_position] = arr[current_position] + 1;
        }
        new_position = current_position * powerB;
        if (new_position >= 0 && new_position <= 100000 && arr[new_position] == 0) {
            q.push(new_position);
            arr[new_position] = arr[current_position] + 1;
        }
    }

    cout << arr[target_position];
        
}