백준 12761번 돌다리

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

백준 1697번 숨바꼭질(http://jaimemin.tistory.com/581)과 유사한 문제였습니다.

8가지 종류에 대해 모두 BFS 알고리즘을 수행하는데 인덱스 범위 초과만 유의해주면 되는 문제였습니다.

#include <iostream>

#include <queue>

#include <algorithm>

using namespace std;

 

const int MAX = 100000 + 1;

 

int A, B, N, M;

bool visited[MAX];

 

int BFS(int idx)

{

        queue<pair<int, int>> q; //idx, cnt

        q.push({ idx, 0 });

        visited[idx] = true;

 

        while (!q.empty())

        {

                 int cur = q.front().first;

                 int cnt = q.front().second;

                 q.pop();

                 if (cur == M)

                         return cnt;

 

                 if (cur + 1 < MAX && !visited[cur + 1])

                 {

                         visited[cur + 1] = true;

                         q.push({ cur + 1, cnt + 1 });

                 }

                 if (cur - 1 >= 0 && !visited[cur - 1])

                 {

                         visited[cur - 1] = true;

                         q.push({ cur - 1, cnt + 1 });

                 }

                 if (cur + A < MAX && !visited[cur + A])

                 {

                         visited[cur + A] = true;

                         q.push({ cur + A, cnt + 1 });

                 }

                 if (cur - A >= 0 && !visited[cur - A])

                 {

                         visited[cur - A] = true;

                         q.push({ cur - A, cnt + 1 });

                 }

                 if (cur + B < MAX && !visited[cur + B])

                 {

                         visited[cur + B] = true;

                         q.push({ cur + B, cnt + 1 });

                 }

                 if (cur - B >= 0 && !visited[cur - B])

                 {

                         visited[cur - B] = true;

                         q.push({ cur - B, cnt + 1 });

                 }

                 if (cur * A < MAX && !visited[cur*A])

                 {

                         visited[cur*A] = true;

                         q.push({ cur*A, cnt + 1 });

                 }

                 if (cur * B < MAX && !visited[cur*B])

                 {

                         visited[cur*B] = true;

                         q.push({ cur*B, cnt + 1 });

                 }

        }      

        return -1;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> A >> B >> N >> M;

 

        cout << BFS(N) << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~