백준 5014번 - 스타트링크

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

현재의 위치에서 목표 위치까지 가기 위한 문제로 

bfs 방식을 통해 층을 옮길 때 몇 번째로 이동했는지 큐에 담아주면 된다.

visited를 통해 방문한 층은 다시 방문하지 않도록 체크하며

올라갈 때 F층을 넘지 않도록, 내려갈 때 0보다 크도록 주의해주면 된다.

이번에는 vector말고 malloc함수를 통해 메모리를 잡아보았다.

마지막에 free를 통해 할당한 메모리를 해제해주면 된다.

참고로 malloc 함수는 int형으로 메모리를 할당할 때

랜덤값으로 할당되서 memset으로 값을 초기화 할 수 있는데

이때 -1만 할당이 가능해서 bool로 메모리를 잡았다.

(물론 -1을 할당한 다음에 -1이 아닐 때로 체크해서 문제를 해결할 수도 있다)

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int main(){
    
    int F,S,G,U,D;
    cin>>F>>S>>G>>U>>D;
    
    bool *visited;
    visited=(bool*)malloc(sizeof(bool)*(F+1));
 
    queue<pair<int,int>> q;
    q.push(make_pair(S,0));
    visited[S]=1;
    
    int ans=-1;
    int stair=0,cnt=0;
    while(!q.empty()){
        stair=q.front().first;
        cnt=q.front().second;
        q.pop();
        
        if(stair==G){
            ans=cnt;
            break;
        }
        
        if(stair+U<=F && !visited[stair+U]){
            q.push(make_pair(stair+U,cnt+1));
            visited[stair+U]=1;
        }
        
        if(stair-D>0 && !visited[stair-D]){
            q.push(make_pair(stair-D,cnt+1));
            visited[stair-D]=1;
        }
        
        
    }
 
    
    free(visited);
 
    if(ans!=-1) cout<<ans<<endl;
    else    cout<<"use the stairs"<<endl;
    
    return 0;
}