백준 5014 : 스타트링크

1. 문제 :  https://www.acmicpc.net/problem/5014

5014번: 스타트링크

 

2. 문제 접근

• 각각의 위치를 노드라고 생각한다면 그래프로 표현할 수 있음 -> 그래프 탐색
• 적어도 몇 번 눌러야하는가 -> 최소한 몇 번 눌러야하는가 -> 최단 거리 탐색 -> BFS

 

3. 문제 해결

1. 중복 노드 방문을 방지하기 위한 벡터 초기화
2. 시작 노드부터 BFS 탐색
3. 노드에서 다른 노드로 이어지는 간선은 총 2개
   • 위로 몇 층 이동할 수 있는지에 대한 U
   • 아래로 몇 층 이동할 수 있는지에 대한 D
4. BFS 종료 후 목표 노드가 반환될 경우 해당 노드의 Depth를 출력, 그렇지 않을 경우 문자열 출력

 

4. 코드

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

int solution(int f, int s, int g, int u, int d)
{
	// Initialize the list for checking whether the node is visited
	vector<bool> visited;
	for (int i = 0; i <= f; i++)
	{
		visited.push_back(false);
	}

	// Find shortest path -> BFS
	// queue item : <depth, position>
	queue<pair<int, int>> bfs;
	bfs.push({ 0, s });
	visited[s] = true;

	while (!bfs.empty())
	{
		pair<int, int> item = bfs.front();
		bfs.pop();

		int depth = item.first;
		int position = item.second;

		// if the node is the target position
		if (position == g)
		{
			return depth;
		}

		// Up direction
		int upPos = position + u;
		// if the node is in range and not visited
		if (upPos <= f && !visited[upPos])
		{
			visited[upPos] = true;
			bfs.push({ depth + 1, upPos });
		}

		// Down Direction
		int downPos = position - d;
		// if the node is in range and not visited
		if (downPos > 0 && !visited[downPos])
		{
			visited[downPos] = true;
			bfs.push({ depth + 1, downPos });
		}
	}

	// Not found
	return -1;
}

int main()
{
	int F, S, G, U, D;

	cin >> F >> S >> G >> U >> D;

	int result = solution(F, S, G, U, D);

	if (result >= 0)
	{
		cout << result << endl;
	}
	else
	{
		cout << "use the stairs" << endl;
	}

	return 0;
}