문제링크:https://www.acmicpc.net/problem/5014
5014번: 스타트링크
문제 강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다. 스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다. 보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없
www.acmicpc.net
버튼의 수의 최솟값을 출력하는 문제로 최단경로값을 구하는 문제였다. 자연스럽게 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;;
}
'알고리즘 > BFS' 카테고리의 다른 글
| [백준] 1389-케빈 베이컨의 6단계 법칙(C++) (0) | 2020.03.22 |
|---|---|
| [백준] 9205-맥주 마시면서 걸어가기(C++) (0) | 2020.03.12 |
| [백준] 2589-보물섬(C++) (0) | 2020.03.08 |
| [백준] 2644-촌수계산(C++) (0) | 2020.03.08 |
| [백준] 7562-나이트의 이동(C++) (0) | 2020.03.08 |