백준 5014번 스타트링크

남마허 2020. 3. 24. 12:51

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

5014번: 스타트링크

문제 강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다. 스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다. 보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없

www.acmicpc.net

<접근방법>

bfs 완전탐색 문제입니다.

엘리베이터로 이동하므로 최소 층과 최대 층이 있음에 유의해야 합니다.

<느낀 점>

<코드>

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

#define max 1000000
int F, S, G, U, D;
bool visit[max + 1];

queue<int> q;

int bfs() {
	q.push(S);
	visit[S] = true;

	int cnt = 0;
	while (!q.empty()) {
		int sz = q.size();
		while (sz--) {
			int now = q.front();
			q.pop();

			if (!(1 <= now && now <= F)) continue;

			if (now == G) {
				return cnt;
			}

			int u = now + U;
			int d = now - D;

			if (u <= max) {
				if (!visit[u]) {
					visit[u] = true;
					q.push(u);
				}
			}
			if (1 <= d) {
				if (!visit[d]) {
					visit[d] = true;
					q.push(d);
				}
			}
		}
		cnt++;
	}

	return -1;
}

int main() {
	cin >> F >> S >> G >> U >> D;

	int ans = bfs();
	if (ans == -1) cout << "use the stairs" << '\n';
	else cout << ans << '\n';

	return 0;
}

저작자표시 (새창열림)