[백준/C++] 12761번 돌다리

 

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

12761번: 돌다리

 

 

#include <bits/stdc++.h>
using namespace std;

template <typename T>
void prt2d(const vector <T>& v1) {
	cout << endl;
	for (int i = 0; i < v1.size(); i++) {
		for (int j = 0; j < v1[i].size(); j++) {
			cout << v1[i][j] << " ";
		}
		cout << endl;
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m, a, b;
	cin >> a >> b >> n >> m;


	// 좌, 우, +a, +b, -a, -b, 우로 a배, 우로 b배
	int dx[8] = { -1, 1, a, b, -a , -b, a, b };

	// 방문 표시 배열
	vector <int> visit(1000000, 0);

	queue <pair <int, int>> q;
	pair<int, int> tmp;

	// 시작점 큐에 삽입, 시작점 -> 시작점의 거리는 0
	q.push({ n, 0 });

	while (!q.empty()) {
		tmp = q.front(); q.pop();
		int now = tmp.first;
		
		// 목적지에 도착하면 종료하고 걸린 시간 출력
		if (m == now) {
			cout << tmp.second;
			break;
		}

		// 8개의 경우를 모두 검사함
		for (int i = 0; i < 8; i++) {
			int nX = 0;

			// 0~5까지는 더하기.  6, 7번 배열은 N배
			if (i > 5) nX = tmp.first * dx[i];
			else nX = tmp.first + dx[i];


			// 배열의 범위에 벗어나지 않게, 방문하지 않은 위치만 방문
			if ((nX > -1 && nX < 100001) && visit[nX] == 0) {

				// 방문 했다면 이전 위치 +1의 시간으로 체크해주고 방문 표시 해줌
				q.push({ nX, tmp.second + 1 });
				visit[nX] = 1;
			}
		}

	}
}