[백준 12761] 돌다리

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

풀이

문제에서 주어진 조건들로 하여금 BFS를 돌리면 됩니다. 해결해야할 조건은 다음과 같습니다.

1. 현위치에서 한칸 왼쪽가기

2. 현위치에서 한칸 오른쪽가기

3. 현위치에서 a칸 왼쪽 가기

4. 현위치에서 a칸 오른쪽가기

5. 현위치에서 b칸 왼쪽 가기

6. 현위치에서 b칸 오른쪽가기

7. 현위치의 a배 왼쪽가기

->현위치의 a배는 무조건 값이 0보다 작게되므로 불가능 

8. 현위치의 a배 오른쪽가기

9. 현위치의 b배 왼쪽가기 

->현위치의 b배는 무조건 값이 0보다 작게되므로 불가능 

10.현위치의 b배 오른쪽가기

총 8가지 조건만 잘 작성하면됩니다.

코드

#include <iostream>
#include<queue>
using namespace std;
int a, b, n, m;
int map[100001], visited[100001], cnt;
void bfs(int start,int  cnt);
int main(void)
{
    cin >> a >> b >> n >> m;
    bfs(n,0);
}
void bfs(int start,int cnt)
{
    queue<pair<int, int>>q;
    q.push({ start,0 });
    visited[start] = 1;
    while (!q.empty())
    {
        start = q.front().first;
        cnt = q.front().second;
        q.pop();
        if (start == m)
        {
            cout << cnt << endl;
            return;
        }
       //한칸 왼쪽 가기
        if(start-1>=0&&!visited[start-1])
        {
            visited[start - 1] = 1;
            q.push({ start - 1,cnt + 1 });
        }
        //한칸 오른쪾 가기
        if (start + 1 <= 100000 && !visited[start + 1])
        {
            visited[start + 1] = 1;
            q.push({ start + 1,cnt + 1 });
        }
 
        //현위치에서 a만큼 왼쪽가기
        if (start - a >= 0 && !visited[start - a])
        {
            visited[start - a] = 1;
            q.push({ start - a,cnt + 1 });
        }
        //현위치에서 a만큼 오른쪽가기
        if (start + a <= 100000 && !visited[start + a])
        {
            visited[start + a] = 1;
            q.push({ start + a,cnt + 1 });
        }
        //현위치에서 b만큼 왼쪽 가기
        if (start - b >= 0 && !visited[start - b])
        {
            visited[start - b] = 1;
            q.push({ start - b,cnt + 1 });
        }
        //현위치에서 b만큼 오른쪽 가기
        if (start + b >= 0 && !visited[start + b])
        {
            visited[start + b] = 1;
            q.push({ start + b,cnt + 1 });
        }
        //현 위치의 a배 오른쪽가기
        if (start *a <= 100000 && !visited[start * a])
        {
            visited[start * a] = 1;
            q.push({ start * a,cnt + 1 });
        }
        
        //현 위치의 b배 오른쪽가기
        if (start * b <= 100000 && !visited[start * b])
        {
            visited[start * b] = 1;
            q.push({ start * b,cnt + 1 });
        }
    }
}

결과