[BOJ / C++] 스타트링크 (BFS)

 

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

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

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

	vector<int> level(1000002, -1);

	queue<int> Q;
	Q.push(s);
	level[s] = 0;

	while (!Q.empty()) {
		int now = Q.front(); Q.pop();
		
		for (int step : {u, -d}) {
			int nxt = now + step;
			if (nxt < 1 || nxt > f) continue;
			if (level[nxt] != -1) continue;

			level[nxt] = level[now] + 1;
			Q.push(nxt);

			if (level[g] != -1) {
				cout << level[g];
				return 0;
			}
		}
	}
	cout << "use the stairs";
}

 

2. 분석

    처음에 level 배열을 0으로 초기화했는데 이 때문에 오류가 발생했었다. level[s]를 처음에 0으로 초기화하고 if (level[nxt] != 0) continue;로 계속 확인했어서 level[s]를 체킹하지 못한 것이다. level 배열 초깃값을 -1로 세팅하고 0부터 시작하면 이 부분이 해결된다!! 앞으로 이 부분을 신경쓰자!

 

3. 시간복잡도

    건물에는 f 층이 있으므로 bfs에서 방문하는 것도 최대 f번이다. 따라서 시간복잡도는 O(f)이다.