BOJ : 12761 돌다리

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

출처

University > 전북대학교 > 2016 전북대 프로그래밍 경진대회 G번

저는 문제를 잘못 이해해서 동규와 주미가 각 턴마다 움직인다는 줄 알았습니다.

알고 보니 스카이 콩콩이 두개..

여튼 문제 해결방법은 BFS를 이용해 각 시간마다 움직일 수 있는 거리를 다 Queue에 push하는 것 입니다.

#include<cstdio>
#include<queue>
using namespace std;

int A, B, N, M, ans = 0;
bool visited[100002];
queue<int> q;

int main() {
    scanf("%d%d%d%d", &A, &B, &N, &M);
    q.push(N);
    visited[N] = 1;
    while (!q.empty()) {
        int sz = q.size();
        while (sz--) {
            int pos = q.front();
            q.pop();
            int next[10] = { 1, -1, A, -A, B, -B, pos*A, -pos*A, pos*B, -pos*B };
            if (pos == M) {
                printf("%d\n", ans);
                return 0;
            }
            for (int i = 0; i < 10; i++) {
                int nextPos;
                if (i < 6) nextPos = pos + next[i];
                else nextPos = next[i];
                if (nextPos < 0 || nextPos >100000) continue;
                if (visited[nextPos]) continue;
                visited[nextPos] = 1;
                q.push(nextPos);
            }
        }
        ans++;
    }
}