[백준 12761] 돌다리 (C++)

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

문제

---

동규와 주미는 일직선 상의 돌 다리 위에있다. 돌의 번호는 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

 

출력

---

동규가 주미에게 도달하기 위한 최소한의 이동 횟수를 출력하라.

 

문제 풀이

---

그래프 탐색 문제.

 

N에서 시작하여 M까지 도달하기 위한 최소 이동 횟수를 구하는 문제이므로 N에서 시작하여 M까지 도달하도록 하는 bfs 탐색을 구현해주면 된다.

큐에 N을 넣고 큐의 front를 가져와 해당 위치에서 이동할 수 있고 아직 방문하지 않은 모든 가능한 위치를 찾아 큐에 넣고 방문 처리한다. bfs 탐색이므로 처음으로 방문하게 되는 M까지의 이동횟수가 정답이 된다.

 

아래는 코드.

#include <iostream>
#include <queue>
#include <utility>
using namespace std;
bool* isVisited;
queue<pair<int, int>> bfsQueue;
int A, B, N, M;

bool isInRange(int N)
{
	if (N >= 0 && N <= 100000)
	{
		return true;
	}
	return false;
}

void bfs()
{
	bfsQueue.push(pair(N, 0));
	isVisited[N] = true;
	while (true)
	{
		pair<int, int> f = bfsQueue.front();
		int current = f.first;
		if (current == M)
		{
			cout << f.second << "\n";
			break;
		}
		int nextPos[] = {current - 1, current + 1, current - A, current + A, current - B, current + B, current * A, current * B};
		for (int i = 0; i < 8; i++)
		{
			int next = nextPos[i];

			if (isInRange(next) && isVisited[next] == false)
			{
				isVisited[next] = true;
				bfsQueue.push(pair(next, f.second+1));
			}
		}
		bfsQueue.pop();
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >>A>>B>> N >> M;
	isVisited = new bool[100001];
	for (int i = 0; i < 100001; i++)
	{
		isVisited[i] = false;
	}
	bfs();
	return 0;
}