백준 5014번 스타트링크

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

 

아이디어:

1. 1697번 숨바꼭질과 같은 2차원 BFS 문제

2. Q.pop() 하면서 cur == G인지 검사하고 출력

3. vis[2000001]은 해당 층에 도달하기 까지 누른 버튼 횟수 (미로의 넓이와 동일)

4. 이동할 때 U는 +로, D는 -로 표현

5. 0층은 존재하지 않으므로 continue, 최대층(F)을 넘기면 continue

 

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int vis[2000001];

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int F, S, G, U, D;
	cin >> F >> S >> G >> U >> D;

	int dx[2] = { U, -D };
	queue<int> Q;
	
	vis[S] = 1;
	Q.push(S);

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

		if (cur == G) {
			cout << vis[cur] - 1;
			return 0;
		}

		for (int dir = 0; dir < 2; dir++) {
			int nx = cur + dx[dir];
			if (nx <= 0 || nx > F) continue;
			if (vis[nx] > 0) continue;
			vis[nx] = vis[cur] + 1;
			Q.push(nx);
		}
	}

	cout << "use the stairs";

	return 0;

}