백준 12761 - 돌다리(C++)

문제 링크입니다. https://www.acmicpc.net/problem/12761

12761번: 돌다리

문제만 길지 어렵지 않은 문제였습니다.

동규가 이동할 수 있는 경우는 8가지입니다.

+1, -1, +A, -A, +B, -B, *A, *B 이렇게 이동할 수 있습니다.

따라서 현재좌표에서 해당 이동 방법을 모두 확인해보고 맞는 경우만 탐색을 이어나가면 됐습니다.

자신의 좌표가 0이상 100,000 이하여야 하니, 해당 조건을 만족하는지부터 확인해줘야합니다.

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>
#include <string>
#define P pair<int, int>
#define F first
#define S second

using namespace std;

int N, M;
int A, B;
int check[100001];

int bfs(){
    queue<P> q; // 현재 좌표, 이동 횟수
    check[N] = 1;
    q.push({N,0});
    while(!q.empty()){
        int x = q.front().F;
        int cost = q.front().S;
        q.pop();
        if(x == M) return cost;
        if(x+1 >= 0 && x+1 <= 100000){
            if(check[x+1] == 0){
                check[x+1] = 1;
                q.push({x+1, cost+1});
            }
        }
        if(x-1 >= 0 && x-1 <= 100000){
            if(check[x-1] == 0){
                check[x-1] = 1;
                q.push({x-1, cost+1});
            }
        }
        if(x+A >= 0 && x+A <= 100000){
            if(check[x+A] == 0){
                check[x+A] = 1;
                q.push({x+A, cost+1});
            }
        }
        if(x+B >= 0 && x+B <= 100000){
            if(check[x+B] == 0){
                check[x+B] = 1;
                q.push({x+B, cost+1});
            }
        }
        if(x-A >= 0 && x-A <= 100000){
            if(check[x-A] == 0){
                check[x-A] = 1;
                q.push({x-A, cost+1});
            }
        }
        if(x-B >= 0 && x-B <= 100000){
            if(check[x-B] == 0){
                check[x-B] = 1;
                q.push({x-B, cost+1});
            }
        }
        if(x*A >= 0 && x*A <= 100000){
            if(check[x*A] == 0){
                check[x*A] = 1;
                q.push({x*A, cost+1});
            }
        }
        if(x*B >= 0 && x*B <= 100000){
            if(check[x*B] == 0){
                check[x*B] = 1;
                q.push({x*B, cost+1});
            }
        }
    }
}

void solve(){
    cout << bfs();
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> A >> B >> N >> M;
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글 남겨주세요!