[BFS] 백준 5014 스타트링크

www.acmicpc.net/problem/5014

5014번: 스타트링크

수행 시간 : 1시간 

 

골드 5 난이도지만 실제 체감 난이도는 한... 실버 1~2 정도로 쉬운문제였다. 엘레베이터 배열을 일차원으로 선언해줘도 되고 범위만 잘 생각해주면 막히는 부분없이 구현 가능한 알고리즘 문제이다.

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int f, s, g, u, d;
bool visited[1000001];

int bfs(int a, int b) { //x는 출발지 y는 도착지
	visited[a] = true;
	queue<pair<int, int>> q;
	q.push(make_pair(a, 0));
	int cnt = 0;
	while (!q.empty()) {
		int x = q.front().first;
		cnt = q.front().second;
		q.pop();
		int nx = x + u * 1;
		int bx = x + d * -1;
		//무조건 up은 f보다 작아야됨 down은 0보다 커야됌
		if (x == b) {
			return cnt;
		}
		if (visited[nx] == false && nx <= f) {
			visited[nx] = true;
			q.push(make_pair(nx, cnt + 1));
		}
		if (visited[bx] == false && bx > 0) {
			visited[bx] = true;
			q.push(make_pair(bx, cnt + 1));
		}
	}
	return -1;
}

void visited_init() {
	for (int i = 1;i < 1000001;i++) {
		visited[i] = false;
	}
}

int main() {
	cin >> f >> s >> g >> u >> d;
	visited_init();
	int ans = bfs(s, g);
	if (ans == -1) {
		cout << "use the stairs";
	}
	else
		cout << ans;

}