[백준] 자동차경주대회

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

2651번: 자동차경주대회

BFS를 이용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, 

출발지와 도착지 사이에 정비소들이 있고, 각 정비소들은 정비시간을 가집니다. 자동차는 한 정비당 갈 수 있는 거리가 정해져 있습니다. 이 때, 총 정비시간을 최소화 해서 도착지점에 도착 했을 때, 거친 정비소, 정비소 갯수, 걸린 시간을 출력해야 합니다.

 

<Solution>

매번 출발지가 있을 것입니다. 처음에는 출발위치에서 출발할 것이고, 이후에는 정비소에서 출발할 것입니다. 

 

매번 출발지에서 갈 수 있는 정비소들에 대해 해당하는 정비소까지의 최소 시간이 갱신되는지 갱신되지 않는지를 살펴보고, 만약 갱신된다면 queue에 다시 넣어서 bfs를 시켜주는 형태로 구현이 가능합니다. 

 

실제 구현은 아래와 같습니다.

구현시 주의해야하는 점은 2^31-1 등의 조건들이 문제에 있으므로, int 자료구조 말고 더 큰 범위를 표현할 수 있는 long long 등을 사용하거나, int 자료구조를 사용하고 싶다면 corner case를 따로 분류하여 문제를 해결하여야 합니다. 

#include <iostream>
#include <queue>
#include <stack>
#include <cstring>
#include <climits>
 
using namespace std;
 
#define MAXN (100)
int L;//정비를 받지 않고 갈수있는 최대거리
int N;//정비소 개수
int dist[MAXN+10];//정비소사이거리
int times[MAXN+10];//정비시간
 
int parent[MAXN+10];
int visited[MAXN+10];
 
void InputData(){
    cin >> L;
    cin >> N;
    for (int i=1; i<=N+1; i++){
        cin >> dist[i];
    }
    for (int i=1; i<=N; i++){
        cin >> times[i];
    }
}
 
 
void solve(){
 
 
    // 만약 바로 도착할수있다면 바로 끝
    int total_dist=0;
    for(int i = 1; i<=N+1; i++){
        total_dist+=dist[i];
    }
    if(L>=total_dist){
        cout << 0 << endl;
        cout << 0 << endl;
        return;
    }
 
    //아니라면 해야함..
    for(int i = 1; i<MAXN+10;i++){
        visited[i] = INT_MAX;
    }
    queue <int> q;
     
    // 출발지 push
    q.push(0);
 
    while(!q.empty()){
        int cur = q.front(); q.pop();
 
        // find reachable places
         
        int next = cur+1;
        int k = dist[next]; // 다음정거장 까지의 거리
        while(k<=L && next<=N+1){
     
            // corner case
            // 총 정비시간이 진짜로 2^31-1일 때
            if(visited[cur]+times[next] == visited[next] && visited[next] == INT_MAX){
                q.push(next);
                parent[next] = cur;
                next++;
                k+= dist[next];
                continue;
            }

            if(visited[cur]+times[next]<visited[next]){
                visited[next] = visited[cur]+times[next];
                q.push(next);
                parent[next] = cur;
            }

            next++;
            k+= dist[next];
        }
    }
 
    cout << visited[N+1] << endl;
 
    stack <int> output_stk;
    int tmp = N+1;
    int cnt = 0;
    while(parent[tmp] !=0){
        cnt++;
        tmp = parent[tmp];
        output_stk.push(tmp);
    }
 
    cout << cnt << endl;
     
    for(int i = 0; i<cnt;i++){
        cout << output_stk.top() << ' ';
        output_stk.pop();
    }
 
    cout << endl;
}
 
 
int main(){
    InputData();
    
    solve();
 
    return 0;
}