백준(C++) 25395번 [커넥티드 카 실험]

 

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

25395번 커넥티드 카 실험

접근방법

현대 s/w 문제집에 있는 커넥티드 카 실험이다.

간단히 정리하면

1. 차 개수와 출발할 시작 위치의 차를 입력 그 후 차 개수만큼 각자의 위치와 연료를 입력

2. 시작 위치에서의 차 연료에 따라 범위를 지정 - 지정한 범위 만큼의 차를 활성화

3. 2번처럼 활성화 된 차 연료의 따라 범위 지정- 범위 내 차를 활성화 (반복)

4. 활성화 된 차를 오름차순으로 정렬 후 출력

 

이다.

 

내가 생각한 방법은 활성화된 차를 스택 또는 큐 같은 공간에 넣은후 조건에 맞는 차를 다시 공간에 넣고 반복 하는것을 생각했다. 이런 문제들을 정형화된 방식으로 푸니깐 코드가 수수께끼 풀이처럼 복잡해 지니 방식을 바꾸기로 했다.

많이 안썻던 struct를 활용하고 함수를 나눠 푸는 방식으로 했다. (전에는 한 코드에 우겨넣듯이 보기에는 간단하게 코드)

결론은 BFS를 사용했고, 조건문은 연료+위치, 연료-위치 로 구현했다.

확실히 코드를 나눠보니 쉽게 구현했다.

 

코드는 다음과 같다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

struct cars
{
    int pos;
    int fuel;
    int index;
};

bool comp(const cars& a, const cars& b)
{
    return a.pos < b.pos;
}
vector<int> bfs(vector<cars>& car, int str){
int n = car.size();
vector<bool> iscar(n,false);
queue<int> q;
vector<int> out;

q.push(str);
iscar[str] = true;
out.push_back(car[str].index+1);

while(!q.empty())
{
    auto cur = q.front();q.pop();

    int left = car[cur].pos - car[cur].fuel;
    int right = car[cur].pos + car[cur].fuel;

    for(int a=cur+1;a<n && car[a].pos <= right;a++)
    {
        if(!iscar[a])
        {
            q.push(a);
            iscar[a] = true;
            out.push_back(car[a].index+1);
        }
    }

    for(int a=cur-1;a>=0 && car[a].pos >= left;a--)
    {
        if(!iscar[a])
        {
            q.push(a);
            iscar[a] = true;
            out.push_back(car[a].index+1);
        }
    }    
    
}

sort(out.begin(),out.end());
return out;


}


int main(void)
{
    cin.tie(0);

    int N,S;
    
    cin >> N >> S;
    vector<int> pos(N);
    vector<int> fuel(N);
    vector<cars> car(N);

    for(int a=0;a<N;a++)
    {
        cin >> pos[a];
    }

   for(int a=0;a<N;a++)
    {
        cin >> fuel[a];
    }    

   for(int a=0;a<N;a++)
    {
        car[a] = {pos[a],fuel[a], a};
    }
    
    sort(car.begin(),car.end(),comp);

    int start = 0;
    for(int a=0;a<N;a++)
    {
        if(car[a].index == S - 1)
        {
            start = a;
            break;
        }
    }

    vector<int> out = bfs(car,start);

    for(int car :  out)cout << car <<" ";

    return 0;
}