[C++] 5014: 스타트링크

골드 Ⅴ

 

#include <iostream>
#include <queue>
using namespace std;

int f, s, g, u, d;
bool visit[1000001];

int bfs() {
	queue<pair<int, int>> q;
	q.push({ s, 0 });

	while (!q.empty()) {
		int cur = q.front().first;
		int cnt = q.front().second;
		q.pop();

		if (cur == g) return cnt;

		for (int i = 0; i < 2; i++) {
			int next;
			if (i == 0) next = cur + u;
			else next = cur - d;

			if (next<1 || next>f) continue;
			if (!visit[next]) {
				visit[next] = true;
				q.push({ next, cnt + 1 });
			}
		}
	}
	return -1;
}

int main() {
	scanf("%d%d%d%d%d", &f, &s, &g, &u, &d);

	int ret = bfs();
	if (ret == -1) printf("use the stairs");
	else printf("%d", ret);
}

 

 

bfs 문제

계속 비슷한 문제만 푸는거 같네!

그 몇 개 전에 있었던 숨바꼭질이랑 너무 똑같은 문제임

 

"x에서 y로 이동하기 위한 최소 cnt 구하기

근데 어떤 x에 있냐에 따라 이동할 수 있는 x' 가 달라짐"

 

을 구하는 문제는 bfs가 정석풀이

dfs로 풀면 시간복잡도가 크게 늘 수 있다

 

-> 이유: 아래 참고!

https://www.acmicpc.net/board/view/53009

글 읽기 - 맞았는데 이문제가 BFS로 풀어야하는 이유가 궁금합니다.