[백준/C++] 스타트링크_5014

📝 문제

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

💻 코드

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int f, s, g, u, d;
int dp[1000001];

int bfs() {
	
	queue<int> q;
	q.push(s);
	dp[s] = 1;

	while (!q.empty()) {
		int now = q.front();
		q.pop();
		if (now == g) {
			return dp[now];
		}

		int nextUp = now + u;
		int nextDown = now - d;
		if (nextUp <= f && !dp[nextUp]) {
			dp[nextUp] = dp[now] + 1;
			q.push(nextUp);
		}
		if (nextDown >= 1 && !dp[nextDown]) {
			dp[nextDown] = dp[now] + 1;
			q.push(nextDown);
		}
	}

	return -1;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> f >> s >> g >> u >> d;
	
	int result = bfs();

	if (result == -1) {
		cout << "use the stairs";
	}
	else cout << result - 1;
	
	return 0;
}

📌 해결방법

1. 시작층부터 bfs()로 가장 먼저 목표층에 도달하는 경우 찾음.

✔ 느낀 점

2차원 배열만 풀다가 1차원으로 접근하니깐 까다로웠다. 문제를 골고루 풀어야겠다😅