백준 5014 스타트링크

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 엘리베이터를 이용해서 U층 만큼 위로 D층 만큼 아래로 갈 수 있는 버튼이 주어지고 현재층에서 목표층까지 최소의 버튼을 누르는 횟수를 구하는 문제입니다. 

bfs를 이용하여 목표층에 도달하는 최소 횟수를 구하면 됩니다. 위 아래 두가지로만 움직일 수 있고 1층 보다 아래로 갈 수 없고 최고층 보다 위로 갈수 없는 조건만 생각하면 특별함은 없는 문제입니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <queue>

using namespace std;

int F, S, G, U, D; //F는 총 건물의 높이 S에서 G층으로 이동 U만큼 위로 D만큼 아래로 이동가능 
int num;
bool flag = true;
queue<int> q;
int visited[1000001];


void bfs() {
	q.push(S);
	visited[S] = 1;
	int ud[2] = {U, -D};
	while(!q.empty()) {
		int len = q.size();
		for(int i = 0; i < len; i++) {
			
			if(q.front() == G) {
				flag = false;
				return;
			}
			
			for(int j = 0; j < 2; j++) {
				int x = q.front() + ud[j];
				
				if(x > F || x < 1)
					continue;
					
				if(visited[x] == 0) {
					q.push(x);
					visited[x] = 1;
				}
			}
			q.pop();
		}
		num++;
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> F >> S >> G >> U >> D;
	bfs();
	if(!flag)
		cout << num;
	else
		cout<<"use the stairs";
	return 0;
}