[백준] No.5014 - 스타트링크 (C++, BFS)

문제

 

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

5014번: 스타트링크

 

풀이

 

solved.ac 난이도: Gold 5

 

간단한 BFS 문제.

 

시작하는 층, S에서 G까지 도달할 수 있는 최소 버튼 push 수를 구해야 한다.

이는 최단 거리를 구하는데 특화된 BFS의 영역이다.

 

특정 층 floor에서 위(floor + U) 또는 아래(floor - D)층으로 이동할 때

이미 방문했다면 해당 층으로 갈 수 있는 최단 push는 이미 구했으므로 더 이상 계산할 필요가 없다.

하지만  방문 하지 않았다면 해당 층으로 가는 최소 push 수는 floor까지 도달하는데 누른 push수의  +1 이다.

 

이를 G에 도달할 때까지 반복하고 만약 도달하지 못하고 BFS가 종료되면 G까지 도달할 수 없다.

 

int PushButtonBFS(int start_floor){
  queue<int> que;
  que.push(start_floor);
  min_push[start_floor] = 0;
 
  int floor, up_floor, down_floor, next_cost;
  while(!que.empty()){
    floor = que.front();
    que.pop();
    
    if(floor == G)
      return min_push[floor];
 
    up_floor = floor +U;
    down_floor = floor - D;
    next_cost = min_push[floor] +1;
    if(up_floor <=F && min_push[up_floor] == -1){
      que.push(up_floor);
      min_push[up_floor] = next_cost;
    }
 
    if(down_floor >=1 && min_push[down_floor] == -1){
      que.push(down_floor);
      min_push[down_floor] = next_cost;
    }
 
  }
 
  return -1;
}

 

 

코드

 

	#include<iostream>
	#include<queue>
	#include<string.h>
	using namespace std;
	const int MAXN = 1000001;
	int F,S,G,U,D;
	int min_push[MAXN];
	int PushButtonBFS(int start_floor){
	queue<int> que;
	que.push(start_floor);
	min_push[start_floor] = 0;
	int floor, up_floor, down_floor, next_cost;
	while(!que.empty()){
	floor = que.front();
	que.pop();
	if(floor == G)
	return min_push[floor];
	up_floor = floor +U;
	down_floor = floor - D;
	next_cost = min_push[floor] +1;
	if(up_floor <=F && min_push[up_floor] == -1){
	que.push(up_floor);
	min_push[up_floor] = next_cost;
	}
	if(down_floor >=1 && min_push[down_floor] == -1){
	que.push(down_floor);
	min_push[down_floor] = next_cost;
	}
	}
	return -1;
	}
	int main(){
	ios_base::sync_with_stdio(0);
	cin>>F>>S>>G>>U>>D;
	memset(min_push, -1, sizeof(min_push) );
	int result = PushButtonBFS(S);
	if(result == -1)
	cout<<"use the stairs\n";
	else
	cout<<result<<"\n";
	return 0;
	}

view raw [BaekJoon]_5014_스타트링크.cpp hosted with ❤ by GitHub