BaekJoon 12761 돌다리

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

소스결과 2216 KB / 4 ms

출처 Baekjoon, 2016 전북대학교 프로그래밍 경진대회

언어 C++ 17

분류 BFS

 

설명

동규와 주미가 돌 다리 위에 있다. 동규가 한번에 +-1 칸을 이동하거나 스카이콩콩을 이용해 +- A B 칸만큼 이동하거나 현재 위치의 A B 배 만큼 이동할 때 동규는 주미를 최소한으로 이동해서 만나는 경우를 구하는 문제

 

일단 문제 자체가 일직선 상의 돌 다리 위 이기 때문에 문제가 간단하다.

또한 한번 방문한 돌은 다시 방문하게 되면 최소 경로가 아니기 때문에 방문 확인 배열이 필요하다.

움직이는 경우의 수는 총 8가지 이다. 현재 위치에서 +- 칸을 이동하거나, +- A B 칸만큼 이동하거나, 현재 위치의 + A B 배 만큼 이동 하는 경우이다.

질문에서는 - A B 배를 포함해 총 10가지라 하지만 실제로는 - A B 배만큼 이동하게 되면 0보다 작으므로 의미가 없다.

 

알고리즘

1. a b n m을 입력 받는다.

2. 현재 위치를 방문한 것으로 판별하고 Queue에 넣는다.

3. 현재 위치에서 +- 1, +- A B, + 현재위치 * A B 를 다음 위치로 계산한다.

4. 3에서 구한 다음 위치가 범위 내의 값이면서 방문하지 않은 점인 경우 다음 방문 Queue에 넣는다.

5. 다음 방문 Queue를 현재 Queue로 만든 후, count 값을 1 증가시킨다.

6. 현재 Queue에서 꺼낸 값이 목표 지점과 일치한다면 탐색을 종료하고 출력한다.

 

소스코드

#include <iostream>
#include <queue>

using namespace std;

const int MAX = 100000;

bool check[MAX + 1];

int pos[8] = { 1, -1 , 1, 1, -1, -1, 1, 1};

int main()
{
	bool isOver = false;
	int count = 0;
	int a, b, n, m;
	queue<int> q;
	queue<int> nextQ;

	cin >> a >> b >> n >> m;

	q.push(n);
	check[n] = true;

	while (!q.empty())
	{
		while (!q.empty())
		{
			int cur = q.front();
			q.pop();

			if (cur == m)
			{
				isOver = true;
				break;
			}

			for (int i = 0; i < 8; i++)
			{
				int next = cur + pos[i]; // 좌우 1칸

				if (i < 2)
					next = cur + pos[i];
				else if (i < 6)
					next = cur + (pos[i] * (i % 2 ? a : b)); // 좌우 A B 칸 이동
				else
					next = cur * (pos[i] * (i % 2 ? a : b)); // 우 현재의 A B 배 이동 ( 좌측은 존재가 불가 )

				if (0 <= next && next <= MAX && !check[next])
				{
					check[next] = true;
					nextQ.push(next);
				}
			}
		}

		if (isOver)
			break;

		while (!nextQ.empty())
		{
			q.push(nextQ.front());
			nextQ.pop();
		}
		count++;
	}

	cout << count;

	return 0;
}