[ 백준 12761 ] 돌다리 (c/c++)

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

 

 

[ 문제 요약 ]

현 위치에서 + 1, - 1, + A, - A, + B, - B, * A, * B 만큼 이동할 수 있고 N에서 M까지 가야할 때, 최소한의 이동 횟수를 출력한다. 단, 이동 과정에서 100,000보다 크거나 0보다 작은 경우는 존재하지 않는다.

 

 

[ 문제 풀이 ]

1. BFS로 첫 위치에서 0 ~ 100,000 사이의 모든 갈 수 있는 곳으로 이동한다.

2. 만약 이미 가 본적 있는 곳이라면 가지 않는다.

3. 한 번 이동할 때마다 이동 횟수를 + 1을 한다.

 

 

[ 소스 코드 ]

#include <bits/stdc++.h>
using namespace std;

int N, M, A, B, num, cnt;
int visited[101010];

void BFS() {
    queue<pair<int, int>> q;
    q.push(make_pair(N, 0));
    visited[N] = 1;

    while (!q.empty()){
        num = q.front().first;
        cnt = q.front().second;
        q.pop();

        if (num == M){
            cout << cnt;
            return;
        }

        int d[] = {num+1, num-1, num+A, num-A,
                    num+B, num-B, num*A, num*B};

        for (int i=0; i<8; i++){
            if (d[i]>=0 && d[i]<=100000){
                if(!visited[d[i]]){
                    visited[d[i]] = 1;
                    q.push(make_pair(d[i], cnt + 1));
                }
            }
        }
    }
}

int main() {
    cin >> A >> B >> N >> M;

    BFS();
    
    return 0;
}

 

 

 

[ 주의할 점 ]

문제의 조건, 0 ~ 100,000 사이만 있다는 것을 못봐서 오랫동안 고민했다.