백준 19238 스타트 택시 (삼성 기출)

www.acmicpc.net/problem/19238

19238번: 스타트 택시

약간의 자료구조 설계와 BFS를 주로 사용하여 해결할 수 있다. 항상 그렇듯이, 이러한 구현 문제는 문제의 조건을 신경 써서 잘 읽고, 흐름과 스토리를 잘 파악해야 한다. 

 

주요한 조건들은 아래와 같다

 

- 승객을 고를 때는 최단거리에 있는 승객을 선택한다.

- 승객마다 가고자 하는 목적지가 있고, 거기까지는 무조건 이동한다. (그 승객의 목적지가 멀다고 승차거부 등을 하지 않는다)

- 이동 중에 연료가 0이되면 실패

- 목적지까지 갔는데 연료가 0이 되면 (재충전이 되므로) 실패로 간주하지 않는다

- 승객을 태우러 간 거리말고, 승객을 태운 상태에서 이동한 거리의 2배가 재충전된다. 

 

여러 번 BFS를 돌려야 함을 직감할 수 있다. 다양한 방법이 있겠지만, 필자가 데이터 정리방식은 다음과 같다.

각 승객의 위치와 목적지들을 pair로 묶어주고 번호(꼬리표)를 달아주었다. 그래서 어떠한 승객이 승차했을 때, 그 승객의 꼬리표가 2번이라면, 2번 목적지랑 매칭 해주는 식이다. 

그리고 BFS함수는 꼬리표번호와 이동해야 할 곳의 좌표 pair를 묶어서 리턴해주는 방식으로 만들었다.

 

이제 풀어가는 방식은:

1. 먼저 승객을 태우러 이동하고, 연료를 확인한다. 

2. 그 승객의 목적지까지 이동하고, 이동중에 연료가 바닥이 나는지 확인한다. 하지만 이동 완료와 동시에 0이 되는 건 괜찮다.

3. (1),(2) 를 마지막 승객까지 반복한다.

 

주의사항:

목적지에 아예 도달할 수 없는 경우 (벽에 막혀있는 등의 이유로)

또는 어떠한 승객을 아예 태울 수가 없는 경우 (위와 같은 이유로)

 

승객정보를 큐나 스택 등에 담을 수는 없다고 생각했다. 각 지점마다 가장 가까운 승객이 누구일지 알 수 없으므로. 대신에 벡터에 담아두고, 서비스 완료 후 erase를 통해 삭제시켜주었다. 칸의 크기 20이라 승객은 최대 200명일 것이라 (20*20/2) 괜찮을 것이라 믿었다(?!).

그리고, BFS를 다 돌리고 (사실 목적지를 찾으면 멈추어도 된다), 목적지 좌표에 해당하는 cost값을 통해 비용을 구하고, 이를 fuel에서 차감하는 식으로 계산하였다.

 

차근차근 실수 없이 풀어내면 어렵지 않게 해결할 수 있다.

 

 

<주요 내용>

시뮬레이션, 구현, BFS

 

<코드>

 

코드는 모듈화도 잘 안되어있고, 분기 처리도 더 깔끔하게 할 수 있을 텐데 그대로 두었다. 양해 부탁드린다.

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
const int sz=20+1;
int nr,nc,cr,cc,a,b,n,m,fuel,board[sz][sz],cost[sz][sz];
int dr[4]={0,1,0,-1},dc[4]={1,0,-1,0};
bool visited[sz][sz];
queue<pair<int,int> >q;
vector<pair<pair<int,int>,int> >goal,passenger;
pair<int,pair<int,int> >now;
pair<int,int> mncoord,goalcoord;

pair<int,pair<int,int> > bfs(pair<int,int>start,int num,bool on){
    memset(visited,0,sizeof(visited));
    memset(cost,0,sizeof(cost));

    q.push(start);
    visited[start.first][start.second]=1;
    int t=0;
    while(!q.empty()){
        t++;
        int qs=(int)q.size();
        for(int k=0;k<qs;++k){
            auto curr=q.front();q.pop();
            cr=curr.first;cc=curr.second;
            for(int i=0;i<4;++i){
                nr=cr+dr[i];
                nc=cc+dc[i];
                if(0<nr && nr<=n && 0<nc && nc<=n && !board[nr][nc] && !visited[nr][nc]){
                    visited[nr][nc]=1;
                    cost[nr][nc]=t;
                    q.push(make_pair(nr,nc));
                }
            }
        }
    }
    int mnidx,mnnum,i=0;
    int mn=n+n+5;
    if(!on){
        for(;i<(int)passenger.size();++i){
            cr=passenger[i].first.first;
            cc=passenger[i].first.second;
            if(!visited[cr][cc]){
                fuel=0;
                return make_pair(0,make_pair(0,0));
            }
            if(cost[cr][cc]<mn){
                mn=cost[cr][cc];
                mnidx=i;
            }
        }
        fuel-=mn;
        mncoord.first=passenger[mnidx].first.first;
        mncoord.second=passenger[mnidx].first.second;
        mnnum=passenger[mnidx].second;
        passenger.erase(passenger.begin()+mnidx);
        return make_pair(mnnum,mncoord);
    }else{
        for(;i<(int)goal.size();++i){
            if(goal[i].second==num){
                if(!visited[goal[i].first.first][goal[i].first.second]){
                    fuel=0;
                    return make_pair(0,make_pair(0,0));
                }
                goalcoord.first=goal[i].first.first;
                goalcoord.second=goal[i].first.second;
                break;
            }
        }
        int c=cost[goalcoord.first][goalcoord.second];
        fuel-=c;
        if(fuel<=0)return make_pair(0,make_pair(0,0));
        fuel+=2*c;
        goal.erase(goal.begin()+i);
        return make_pair(0,goalcoord);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    cin>>n>>m>>fuel;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            cin>>board[i][j];
        }
    }
    cin>>now.second.first>>now.second.second;
    for(int i=0;i<m;++i){
        cin>>a>>b;
        passenger.push_back(make_pair(make_pair(a,b),i));
        cin>>a>>b;
        goal.push_back(make_pair(make_pair(a,b),i));
    }
    sort(passenger.begin(),passenger.end());
    while(!goal.empty()){
        now=bfs(now.second,0,0);
        if(fuel<=0){
            cout<<-1<<endl;
            return 0;
        }
        now=bfs(now.second,now.first,1);
        if(fuel<=0){
            cout<<-1<<endl;
            return 0;
        }
    }
    cout<<fuel<<endl;
    return 0;
}