백준 5014 c++ " 스타트링크" -PlusUltraCode-

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

 

[필자 사고]

BFS 탐색 문제다.

인기 있는 일직선상 원하는 위치로 이동하는 문제와 동일하게 접근하면 쉽게 풀 수있다.

다만 조심해야 되는 점은 아래층으로 갈때 더하는게 아니고 빼야 된다는 점이다.

필자는 이 부분에서 애를 먹고 계속 오류를 범했다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

Input 함수

이 함수는 사용자로부터 입력을 받는 역할을 합니다.
총 F층짜리 건물에서 시작 층 S에서 목표 층 G로 이동하기 위해, 위로 U층 혹은 아래로 D층씩 이동 가능한 설정을 입력받습니다.
입력값에 따라 visited 배열과 dx 벡터를 초기화합니다.

• visited는 각 층을 방문했는지를 기록하는 배열입니다.
• dx는 이동할 수 있는 방향과 칸 수를 저장하는 배열입니다. 이때 문제는 D를 양수로 저장한 것이며, 아래로 이동하려면 -D로 저장해야 합니다.

---

BFS 함수

이 함수는 너비 우선 탐색(BFS)을 통해 최단 횟수로 목표 층 G에 도달하는 방법을 찾습니다.

• 시작 위치와 횟수를 큐에 저장하고, 방문 처리를 합니다.
• 큐가 빌 때까지 반복하면서 현재 위치에서 위 또는 아래로 이동 가능한 다음 층을 계산합니다.
• 각 이동이 가능한 층(1 <= 층 <= F)이며 아직 방문하지 않았다면 큐에 추가하고 방문 처리합니다.
• 목표 층에 도달하면 해당 시점의 횟수를 출력하고 함수를 종료합니다.
• 큐를 모두 처리했는데도 목표에 도달하지 못하면, 도달 불가능하다는 의미로 "use the stairs"를 출력합니다.

---

Game_Start 함수

실제로 BFS 탐색을 시작하는 함수입니다.
초기 시작층과 시작횟수 0을 넘겨 BFS를 호출합니다.

---

main 함수

프로그램의 진입점입니다.
입력을 받고, 게임 로직을 시작하는 순서로 함수를 호출합니다.

---

요약 문제점

• dx 배열에서 위로 가는 U는 맞지만, 아래로 가는 D도 양수로 처리한 것이 문제입니다.
• 아래 방향은 음수인 -D로 처리해야 올바르게 작동합니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> Node;
int F, S, G, U, D;
vector<bool> visited;
queue<Node> myQueue;

vector<int> dx;

void Input() {
	cin >> F >> S >> G >> U >> D;
	visited.resize(1000000+1,false);
	dx.resize(2);
	dx[0] = U;
	dx[1] = -D;
}

void BFS(int start, int count) {
	myQueue.push({ start,count });
	visited[start] = true;

	while (!myQueue.empty()) {
		int nowStart = myQueue.front().first;
		int nowCount = myQueue.front().second;

		if (nowStart == G) {
			cout << nowCount;
			return;
		}
		myQueue.pop();

		for (int i = 0; i < 2; i++) {
			int nextStair = nowStart + dx[i];

			if (nextStair >= 1 && nextStair <= F
				&& visited[nextStair]==false) {
				myQueue.push({ nextStair,nowCount + 1 });
				visited[nextStair] = true;
			}
		}

	}
	cout << "use the stairs";
}

void Game_Start() {
	BFS(S, 0);
}

int main(void) {
	Input();
	Game_Start();
}