[백준] 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;
}

 

 

코드