[백준] 5014-스타트링크(C++)

문제링크:https://www.acmicpc.net/problem/5014

5014번: 스타트링크

 

 

버튼의 수의 최솟값을 출력하는 문제로 최단경로값을 구하는 문제였다. 자연스럽게 bfs로 해결할 수 있음을 인지해서 그렇게 풀었다. 

 

 

 

 

 

첫번째로 조심해야할 조건은 만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다 이다. 이동할 수 없으면 그자리에서 이동하지 않는다.

 

첫번째 조건은 문제를 읽고 인지하고 있었기 때문에 문제가 되지 않았는데, 두 번째 예외가 있었다. 출발점과 도착점이 같은경우에는 0을 출력해줘야 하는 문제점이다. 

 

그래도 틀린다면 한가지 테스트 케이스를 돌려보세요. 10 5 4 0 1 .......

감이 오시나요?? 저는 이 예외를 인지하지 못해서 엄청 고통받았습니다.

 

 

 

아마 틀리셨다면 위 3개의 조건중에 해답이 있을 거라고 생각합니다. 예외처리 이외의 문제 구현은 어려움이 없으셨을 거라고 생각합니다. 

 

아래는 정답코드입니다.

#include <iostream>
using namespace std;
int f, s, g, u, d;
int que[1000001];
int start=0, ended=0;
int visited[1000001] = { 0 };

void bfs() {

	que[ended++] = s;

	while (start != ended) {

		int current = que[start++];

		if (current + u <= f && !visited[current + u]&& u!=0) {
			visited[current + u] = visited[current] + 1;
			que[ended++] = current + u;
		}
		if (current - d > 0 && !visited[current - d] && d!=0) {
			visited[current - d] = visited[current] + 1;
			que[ended++] = current - d;
		}

	}
}

int main() {
	cin >> f >> s >> g >> u >> d;

	bfs();

	if (!visited[g] && f != s)
		cout << "use the stairs" << endl;
	else
		cout << visited[g] << endl;;
}