BOJ 19238, 스타트택시

Source: BOJ 19238 스타트 택시

스타트 택시

정답비율이 많이 낮았던 문제라 마음을 굳게 먹고 풀었던 문제이다

문제를 요약해 보자면 입력으로 벽과 보드판, 택시의 위치, 연료의 양, 승객과 목적지의 위치가 주어진다

주어진 승객의 위치 중에서 현재 택시의 위치와 가장 가까운 승객을 태우러 가고

그 승객의 목적지 까지 데려다 준다 (반복)

(단, 벽에 막혀 갈 수 없거나 연료가 부족하여 목적지 또는 승객을 태우러 갈 수 없을 경우 -1 을 출력한다)

최종적으로 모든 승객을 태우고 목적지까지 도착 할 수 있다면 마지막으로 남은 연료의 양을 출력하는 문제!

문제를 해결하기 위해 승객의 위치, 목적지는 2차원 벡터 info안에 담았고

solution함수를 통해 bool형 재귀를 구현, dist함수를 통해 두개의 위치좌표의 거리를 반환하는 과정을 통해 문제를 해결할 수 있었다

---

PS Logic

1. 입력으로 주어질 보드판 -> int board[21][21] (빈칸: 0, 벽: 1)

2. 태운 승객을 마킹 -> bool vis[401]

3. 승객의 위치와 목적지 위치를 담을 2차원 벡터 vector<vector> info

4. info를 돌면서 현재 택시의 위치와 승객의 거리를 반환하는 dist()를 통해 가장 가까운 승객을 선택

5. 선택한 승객과의 거리가 남아있는 연료보다 클 때와 갈 수 없을 때 return false

6. else의 경우라면 택시의 위치와 남아있는 연료를 update

7. 다시 한번 dist()를 통해 현재 택시의 위치와 목적지 위치의 거리 계산

8. 거리가 남은 남아있는 연료보다 클 때와 갈 수 없을 때 return false

9. else의 경우라면 택시의 위치와 남아있는 연료를 다시 update

10. 반복한 후 모든 승객을 태우면 남아있는 연료 출력

---

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};
int n, m;
int fuel;
bool vis[401];
vector<vector<int>> info;
int board[21][21];

int dist(int from_x, int from_y, int to_x, int to_y){
  if(from_x == to_x && from_y == to_y) return 0;
  queue<pair<int, int>> q;
  int d[21][21] = {0,};
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      d[i][j] = -1;
    }
  }
  d[from_x][from_y] = 0;
  q.push({from_x, from_y});
  while(!q.empty()){
    auto cur = q.front();
    q.pop();
    for(int dir = 0; dir < 4; dir++){
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir];
      if(nx<0 || ny<0 || nx>=n || ny>=n)continue;
      if(board[nx][ny] == 1 || d[nx][ny]>=0) continue;
      q.push({nx, ny});
      d[nx][ny] = d[cur.X][cur.Y] + 1;
      if(nx == to_x && ny==to_y) return d[nx][ny];
    }
  }
  return -1;
}

bool solution(vector<vector<int>> info, int taxi_x, int taxi_y, int cnt){
  if(cnt == m){
    return true;
  }
  
  //방문하지 않은 승객 중, 가장 가까운 승객 찾기
  int mndist = 0x7f7f7f7f;
  pair<int, int> passenger;
  pair<int, int> destination;
  int vis_idx;
  for(int i=0; i<m; i++){
    if(vis[i]) continue;
    int d = dist(info[i][0], info[i][1], taxi_x, taxi_y);
    if(d == -1) return false;
    if(mndist>d){
      mndist = d;
      passenger = {info[i][0], info[i][1]};
      destination = {info[i][2], info[i][3]};
      vis_idx = i;
    }
    
  }
  //연료가 부족하면 false
  if(mndist > fuel){
    return false;
  }

  taxi_x = passenger.X;
  taxi_y = passenger.Y;
  fuel -= mndist;

  int d = dist(taxi_x, taxi_y, destination.X, destination.Y);
  if(d == -1 || d > fuel){
    return false;
  }
  
  taxi_x = destination.X;
  taxi_y = destination.Y;
  fuel += d;
  vis[vis_idx] = true;
  cnt++;
  return solution(info, taxi_x, taxi_y, cnt);
}


int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin>>n>>m>>fuel;

  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      cin>>board[i][j];
    }
  }
  int taxi_x, taxi_y;
  cin>>taxi_x>>taxi_y;
  taxi_x--, taxi_y--;
  for(int i=0; i<m; i++){
    vector<int> v;
    for(int j=0; j<4; j++){
      int s;
      cin>>s;
      s--;
      v.push_back(s);
    }
    info.push_back(v);
  }
  sort(info.begin(), info.end());
  bool pos = solution(info, taxi_x, taxi_y, 0);
  int ans = pos ? fuel : -1;
  cout<<ans;
}