백준(BOJ) 19238 : 스타트 택시

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

19238번: 스타트 택시

 

문제가 워낙 기니 문제 설명은 링크를 가서 읽어주시길..

 

문제를 보면 알겠지만 딱 BFS 구현문제다.

 

개인적으로는

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

16236번: 아기 상어

이 문제와 매우매우 비슷하다 느꼈다.

난이도를 굳이 따지자면 이 문제가 조금 더 어렵다고 느껴지는 듯.

 

우선 문제를 풀기 위해 필요한 조건은 다음과 같다.

 

1. 백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 

2. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을 태운다.

3. 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다.

4. 연료는 한 칸 이동할 때마다 1만큼 소모된다.

5. 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료 양의 두 배가 충전된다.

6. 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그 날의 업무가 끝난다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.

7. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.

 

 

문제를 손님을 찾아서 택시에 태우는 과정과 손님을 목적지까지 이동시키는 함수 두개를 통해 해결하자.

먼저 손님을 찾아서 택시에 태워야하니 최단거리의 손님을 찾자.

만약 최단거리가 같다면 행 번호가 작은 손님, 열 번호가 작은 손님을 태워야하니 최단거리의 손님들을 모아놓은 벡터를 오름차순으로 정렬했을 때에 0번째 인덱스 손님이 가장 적합한 손님이 될 것이다!

그 때, 현재의 연료 - 손님의 거리를 했을 때에 연료가 바닥나거나 찾을 수 있는 손님이 존재하지 않을 경우에 -1을 해주면 되겠다!

 

 

이제 손님을 이동시키도록 하자.

목적지까지의 거리가 연료만큼이라면 충분히 손님을 이동시킬 수 있으며 연료보다 크다면 -1을 출력시켜주면 될 것이다.

만약 가능하다면 두배의 연료가 충전되므로 현재 연료에서 거리만큼만 더해주면 되겠다. (소비한 연료를 빼주지 않았으므로 두배가 아닌 한번만 더해주면 된다.) 

 

이제 위 과정을 반복하며 손님을 태워 도착한 횟수가 M번 일 때 프로그램을 종료하면 되겠다.

 

아래는 소스코드이다.

 

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define cont continue
#define rep(i, n) for(int i = 0 ; i < (n) ; i++)
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 987654321;

int N, M, fuel;
int board[21][21] = {};
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
bool visit[21][21] = {};
int startrow, startcol;
queue<pair<pii, int> > q;
vector<pii> goodcus;
vector<pii> st;
vector<pii> dest;
bool flag = true;
int takey = 0;
int takex = 0;
int taked = 0;
int d_p_y = 0;
int d_p_x = 0;
int idx = -1;
bool taken[401] = {};

bool isRange(int y, int x) {
  if(y <= 0 || y > N || x <= 0 || x > N) return false;
  else return true;
}

void findcustomer() {
  int mind = INF;
  while(!q.empty()) {
    int cury = q.front().first.first;
    int curx = q.front().first.second;
    int curd = q.front().second;
    q.pop();
    visit[cury][curx] = true;
    bool z = false;
    for(int i = 0 ; i < st.size() ; i++) {
      if(st[i].first == cury && st[i].second == curx && taken[i] == false) {
        z = true;
      }
    }
    if(z) {
      if(curd < mind) {
        goodcus.clear();
        goodcus.pb(mp(cury, curx));
        mind = curd;
      }
      else if(curd == mind) {
        goodcus.pb(mp(cury, curx));
      } 
    }
    for(int i = 0 ; i < 4 ; i++) {
      int ny = cury + dy[i];
      int nx = curx + dx[i];
      if(!isRange(ny, nx)) continue;
      if(!visit[ny][nx] && board[ny][nx] != 1) {
        visit[ny][nx] = true;
        q.push(mp(mp(ny, nx), curd + 1));
      }
    }
  }

  if(fuel - mind <= 0 || goodcus.size() == 0) {
    flag = false;
    return;
  }

  fuel -= mind;
  sort(goodcus.begin(), goodcus.end());
  takey = goodcus[0].first;
  takex = goodcus[0].second;
  for(int i = 0 ; i < st.size() ; i++) {
    if(st[i].first == takey && st[i].second == takex) {
      idx = i;
      taken[i] = true;
      break;
    } 
  }
  d_p_y = dest[idx].first;
  d_p_x = dest[idx].second;
  board[takey][takex] = 0;
}

void move() {
  q.push(mp(mp(takey, takex), 0));
  bool yes = false;
  while(!q.empty()) {
    int cury = q.front().first.first;
    int curx = q.front().first.second;
    int curd = q.front().second;
    q.pop();
    visit[cury][curx] = true;
    if(cury == dest[idx].first && curx == dest[idx].second) {
      yes = true;
      startrow = cury;
      startcol = curx;
      board[cury][curx] = 0;
      fuel += curd;
      taked++;
      while(!q.empty()) q.pop();
      break;
    }

    if(fuel - curd <= 0) {
      flag = false;
    }

    for(int i = 0 ; i < 4 ; i++) {
      int ny = cury + dy[i];
      int nx = curx + dx[i];
      if(!isRange(ny, nx)) continue;

      if(!visit[ny][nx] && board[ny][nx] != 1) {
        visit[ny][nx] = true;
        q.push(mp(mp(ny, nx), curd + 1));
      }
    }
  }
  if(!yes) flag = false; 
  else return;
}

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

  cin >> N >> M >> fuel;
  for(int i = 1 ; i <= N ; i++) {
    for(int j = 1 ; j <= N ; j++) {
      cin >> board[i][j]; 
    }
  }
  cin >> startrow >> startcol;
  
  for(int i = 2 ; i <= 2 * M ; i += 2) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    st.pb(mp(a, b));
    dest.pb(mp(c, d));
  }

  while(taked != M) {
    while(!q.empty()) q.pop();
    q.push(mp(mp(startrow, startcol), 0));
    memset(visit, false, sizeof(visit));

    findcustomer();
    while(!q.empty()) q.pop();
    if(!flag) {
      cout << "-1" << endl;
      return 0;
    }

    memset(visit, false, sizeof(visit));

    move();

    if(!flag) {
      cout << "-1" << endl;
      return 0;
    }
  }
  cout << fuel << endl;
}