백준 12761 돌다리

12761번: 돌다리

문제

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

 

풀이

BFS문제이다. 동규가 갈 수 있는 길은 총 8가지 이다.

1. +1

2. -1

3.+A

4.-A

5.+B

6.-B

7.N*A

8.N*B

queue<pair<int,int>> q;

pair<int,int> 를 사용해 first에는 현재 돌의 위치, second에는 이동횟수를 넣어줬다.

BFS를 사용하면 최단 이동횟수를 구할 수 있다. 방문 배열을 만들어 이미 방문한 돌은 다시 갈 수 없게 해줘야 한다. (처음에 깜빡하고 안만들었다가 두번째 테스트케이스에서 막혔다ㅠㅠ)

*주의: 0 <= crnt && crnt <= 100,000

#include <iostream>
#include <queue>
#define MAX 100001
 
using namespace std;
 
bool visited[MAX];
 
int plusfunc(int i,int a, int b, int crnt)
{
    int k[8] = { crnt*a, crnt*b,crnt + a,crnt + b,crnt + 1,
    crnt - a,crnt - b,crnt - 1 };
    return k[i];
}
 
 
int bfs(int a,int b,int n,int m)
{
    queue<pair<int,int>> q;
    int ans;
    q.push(make_pair(n, 0));
    visited[n] = true;
    while (!q.empty()) {
        const int crnt = q.front().first;
        const int cnt = q.front().second;
        q.pop();
        if (crnt == m) {
            ans = cnt;
            break;
        }
        else {
            for (int i = 0; i < 8; ++i) {
                int nx = plusfunc(i, a, b, crnt);
                if (nx < MAX  && nx >= 0&& !visited[nx]) {
                    q.push(make_pair(nx, cnt + 1));
                    visited[nx] = true;
                }
            }
        }
 
    }
    return ans;
}
 
int main(void)
{
    int a, b, n, m;
    cin >> a >> b >> n >> m;
    
    cout << bfs(a, b, n, m) << endl;
 
    return 0;
}