문제
동규와 주미는 일직선 상의 돌 다리 위에있다. 돌의 번호는 0 부터 100,000 까지 존재하고 동규는 N번 돌 위에, 주미는 M번 돌 위에 위치하고 있다. 동규는 주미가 너무 보고싶기 때문에 최대한 빨리 주미에게 가기 위해 A,B 만큼의 힘을 가진 스카이 콩콩을 가져왔다. 동규가 정한 다리를 건너는 규칙은 턴 방식인데, 한 턴에 이동할 수 있는 거리는 이러하다. 현 위치에서 +1칸, -1칸을 이동할 수 있고, 스카이 콩콩을 이용해 현 위치에서 A나 B만큼 좌우로 점프할 수 있으며, 순간적으로 힘을 모아 현 위치의 A배나 B배의 위치로 이동을 할 수 있다. 예를 들어 지금 동규가 7번 돌 위에 있고 스카이 콩콩의 힘이 8이면 그냥 점프를 해서 15번 돌에 갈 수도 있고, 순간적으로 힘을 모아 56번 돌에 갈 수도 있다는 것이다. 주어진 8가지의 방법 중 적절한 방법을 골라서 최대한 빨리 동규가 주미를 만날 수 있게 도와주자. 단, 이동 과정에서 100,000보다 크거나 0보다 작은 번호의 돌은 존재하지 않으므로 갈 수 없고, 같은 방법을 계속 사용해도 되며 항상 도달할 수 있는 케이스만 주어진다.
입력
입력의 첫 줄에 스카이 콩콩의 힘 A와 B, 그리고 동규의 현재위치 N, 주미의 현재 위치 M이 주어진다. (단, 2≤A,B≤30 이고 0≤N,M≤100,000)
출력
동규가 주미에게 도달하기 위한 최소한의 이동 횟수를 출력하라.
풀이
#include<queue>
#include<iostream>
#include<algorithm>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
#define MAX 100001
int A, B, N, M;
int visited[MAX] = { 0, };
int bfs() {
queue<pair<int, int>> need_visit;
visited[N] = 1;
need_visit.push({ N, 0 });
while (!need_visit.empty()) {
int node = need_visit.front().first;
int count = need_visit.front().second;
need_visit.pop();
if (node == M)
return count;
int temp[8] = { node - B, node - A, node - 1, node + 1, node + A, node + B,
node * A, node * B };
for (int i = 0; i < 8; i++) {
if (temp[i] >= 0 && temp[i] < MAX) {
if (visited[temp[i]] == 0) {
visited[temp[i]] = 1;
need_visit.push({ temp[i], count + 1 });
}
}
}
}
}
int main() {
cin >> A >> B >> N >> M;
cout << bfs();
}
'알고리즘 > 백준 문제풀이' 카테고리의 다른 글
[백준 2667번] 단지번호붙이기 / C++ (0) | 2020.08.19 |
---|---|
[백준 2012번] 등수 매기기 / C++ (0) | 2020.08.18 |
[백준 1904번] 01타일 / C++ (0) | 2020.08.13 |
[백준 1325번] 효율적인 해킹 / C++ (메모리 초과) (0) | 2020.08.13 |
[백준 1012번] 유기농 배추 / C++ (0) | 2020.08.13 |