[알고리즘/문제풀이][BOJ 5014번] 스타트링크

스타트링크 문제는 BFS를 사용하여 해결할 수 있는 문제입니다. 시작 층을 하나의 노드로, 도착 층을 하나의 노드로 생각하고 U, D 버튼을 다른 노드로 가는 간선을 나타낸다고 생각하면 BFS로 생각할 수 있습니다.

최소한으로 버튼을 눌러서 도착하기 위해서는 BFS를 사용하여 U, D 버튼으로 이동가능한 모든 노드를 탐색해야 합니다.

BFS에 대한 설명은 다음의 게시물에서 확인할 수 있습니다.

2021.09.07 - [알고리즘/문제풀이] - [알고리즘/문제풀이][BOJ 1260번] DFS와 BFS

[알고리즘/문제풀이][BOJ 1260번] DFS와 BFS

작성한 코드는 다음과 같습니다.

#include<stdio.h>
#pragma warning(disable : 4996)

int F, S, G, U, D;
int visit[1000020];

int queue[1000020];
int wp, rp;
int check = 0;

void BFS() {
	queue[wp++] = S;
	visit[S] = 1;

	while (rp != wp) {
		int temp = queue[rp++];
		if (temp == G) {
			printf("%d\n", visit[temp]-1);
			check = 1;
			return;
		}
		if (temp + U <= F) {
			if (visit[temp + U] == 0) {
				queue[wp++] = temp + U;
				visit[temp + U] = visit[temp] + 1;;
			}
		}
		if (temp - D >= 1) {
			if (visit[temp - D] == 0) {
				queue[wp++] = temp - D;
				visit[temp - D] = visit[temp]+1;
			}
		}
	}
}

int main(void) {
	scanf("%d %d %d %d %d", &F, &S, &G, &U, &D);

	BFS();
	if (check == 0) printf("use the stairs");

}

문제는 다음의 링크에서 확인할 수 있습니다.

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