백준 문제 5014번 스타트링크

 

백준 문제 5014번 스타트링크

---

문제 풀러 가기

5014번: 스타트링크

 

#include <iostream>
#include <queue>

using namespace std;

typedef struct myVertex {
public:
	int floor;
	int cnt;
}vertex;

int BFS(int start, int dest, int up, int down, int max)
{
	bool* found = new bool[max+1]{false,};
	queue<vertex> q;//확인할 값들
	int temp[2] = { up, -down }; //위, 아래 이동할때
	vertex now = { start, 0 };
	vertex next = { 0, 0 };

	q.push(now);
	found[now.floor] = true;

	while (!q.empty()) {
		now = q.front(); q.pop();
		if (now.floor == dest) {
			return now.cnt;
		}

		//up, down 조사
		for (int i = 0; i < 2; i++) {
			next.floor = now.floor + temp[i];
			next.cnt = now.cnt + 1;
			if (next.floor > max || next.floor <= 0) continue;
			if (found[next.floor]) continue;
			q.push(next);
			found[next.floor] = true;
		}

	}

	return -1;
}

int main() {

	int f, g, s, u, d;
	cin >> f >> s >> g >> u >> d;
	int res = BFS(s, g, u, d, f);
	res != -1 ? cout << res : cout << "use the stairs";

	return 0;
}

위의 코드가 나의 코드이다.

 

나는 BFS를 이용하여 풀었고, 층, 몇 번 이동해서 그 층에 도달했는지를 저장할 정점을 구조체를 하나 만들어서 사용하였다.

 

temp 배열에 up과 -down을 저장해놔서 for문을 2번 돌면서 범위를 이탈하거나 이미 갔던 층이라면 가지 않도록 했다.

그리고 원래 층의 구조체에서 +up 또는 -down을 하고 카운트를 +1 하여서 구조체를 queue 구조의 공간에 넣어주었다.

그런식으로 너비 우선 탐색을 진행했다.

 

풀던 중 발생한 문제, 그리고 해결

---

처음에는 틀렸다고 나왔다. 그 이유는 아래와 같이 0일때 "use the stairs"를 출력해줬기 때문이다.

return 0

res != 0 ? cout << res : cout << "use the stairs";

모든 정점을 다 확인해봤지만 스타트링크의 층으로 갈 수 없다면 "use the stairs"를 출력해주어야 한다.

그래서 위와 같이 코드를 짰지만 문제가 있었다.

 

만약에 이미 스타트링크 회사가 있는 층에 와 있다면? 이미 도착했기 때문에 아마 0이 나올 것이다.

그렇기 때문에 위의 코드는 문제가 되는 것이었다.

 

그래서 나는 스타트링크의 층으로 갈 수 없다면 -1을 리턴해주고, -1일때 "use the stairs"를 출력해주도록 바꿔주었다!

 

바꿔주니 맞았다!

이런 작은 부분도 신경 써서 문제를 풀어야 한다는 것을 다시 한 번 느꼈다!

 

다짐

---

작은 부분도 신경 쓰기! 🧚‍♀️