[BFS] 12761번 돌다리

12761번 돌다리

 

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

 

문제

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

 

입력

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

 

출력

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

 

예제 입력

2 3 1 20

3 7 2 98500

 

예제 출력

4

10

 

해결방법

1차원 배열에서 여러 경우의 수로 최단 거리를 찾는 BFS 탐색 문제이다

 

 

⭐️ 솔루션 ⭐️

큐에서 꺼낸 뒤, 8가지 경우의 수를 모두 구현하면 된다 !!

 

사실 구현은 아주 간단했다

지정된 범위보다 벗어나서 다시 돌아오는 경우가 있을거라 생각했는데 문제에서 범위를 벗어나는 돌다리는 없다고 명시해줘서 아무 막힘없이 구현할 수 있었다

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 100001
#define INF 987654321
using namespace std;

struct node {
    int now,cnt;
    
    node() { }
    node(int _n,int _c) : now(_n),cnt(_c) { }
};

int n,m,a,b;

bool visited[MAX];

void bfs(){
    queue<node> q;
    q.push(node(n,0));
    visited[n] = true;
    
    while(!q.empty()){
        int now = q.front().now;
        int cnt = q.front().cnt;
        q.pop();
        
        // 정답을 찾은 경우
        if(now == m){
            cout << cnt << "\n";
            return;
        }
        
        // 앞으로 한칸 이동
        if(now+1 < MAX && !visited[now+1]){
            q.push(node(now+1,cnt+1));
            visited[now+1] = true;
        }
        
        // 뒤로 한칸 이동
        if(now-1 >= 0 && !visited[now-1]){
            q.push(node(now-1,cnt+1));
            visited[now-1] = true;
        }
        
        // 앞으로 A칸 이동
        if(now+a < MAX && !visited[now+a]){
            q.push(node(now+a,cnt+1));
            visited[now+a] = true;
        }
        
        // 앞으로 b칸 이동
        if(now+b < MAX && !visited[now+b]){
            q.push(node(now+b,cnt+1));
            visited[now+b] = true;
        }
        
        // 뒤로 A칸 이동
        if(now-a >= 0 && !visited[now-a]){
            q.push(node(now-a,cnt+1));
            visited[now-a] = true;
        }
        
        // 뒤으로 b칸 이동
        if(now-b >= 0 && !visited[now-b]){
            q.push(node(now-b,cnt+1));
            visited[now-b] = true;
        }
        
        // 앞으로 now*A칸 이동
        if(now*a < MAX && !visited[now*a]){
            q.push(node(now*a,cnt+1));
            visited[now*a] = true;
        }
        
        // 앞으로 now*B칸 이동
        if(now*b < MAX && !visited[now*b]){
            q.push(node(now*b,cnt+1));
            visited[now*b] = true;
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> a >> b >> n >> m;
    
    memset(visited, false, sizeof(visited));
    
    bfs();
    
    return 0;
}