[C++] BOJ 19238 - 스타트 택시

 

 

BOJ 19238 - 스타트 택시 (https://www.acmicpc.net/problem/19238)

 

01. 🔎 문제 탐색

N: 활동 영역 (NxN의 영역, N <= 20)
    영역의 칸 상태 (0: 빈 칸, 1: 벽)
M: 목표 승객 수 ($M <= N^2$)
초기연료 <= 500,000

• 택시는 항상 최단경로로 이동
  • 현재 위치에서 가장 거리가 짧은 승객 우선 (거리가 같을 경우 아래의 우선 순위를 따름)
    • 행 번호가 가장 작은 승객 우선
    • 열 번호가 가장 작은 승객 우선
  • 위치가 같은 경우, 거리는 0
  • 연료는 1칸당 1씩 소모
  • 목적지에 도착 시, 승객을 태우고 소모한 연료의 2개가 충전 (초기 연료를 초과하여 충전도 가능)
  • 이동도중, 연료가 바닥나면 이동 실패 -> 하루 업무 종료
  • 만약, 목적지 도착과 동시에 연료 바닥 시에 이동 성공 판정
• OUTPUT
  모든 승객을 성공적으로 데려다주고 남은 연료의 양을 출력
  만약, 실패 시 -1을 출력

01-1. 가능한 시간 복잡도

• 시간 제한 1초, N의 최대가 20으로 시간 복잡도 $O(N^k)$ 도 가능

01-2. 알고리즘 선택

• BFS를 이용한 시뮬레이션 문제
• 가까운 승객 탐색 최악의 경우, (400 + 4) * 400 의 연산 횟수로 시간 복잡도 $O((V + E) * N^2)$
• 승객의 위치에서 목적지 최단 거리 탐색, (400 + 4)로 시간 복잡도 $O(V+E)$
• 최악의 경우, 400명의 승객을 태우는 동안, BFS 연산이 2번 필요 400*2*(400 + 4) = 323,200 번의 연산으로 충분히 가능

02. 📝 코드 설계하기

1. 영역에 대한 정보 (0: 빈 칸, 1: 벽)와 초기 연료에 대한 정보를 입력받음
2. 택시 위치를 입력받아 현재 위치로 저장 -> taxi
3. 고객의 현재 위치와 고객의 목적지를 벡터에 각각 저장 -> [customers, goal]
4. 현재 택시 위치에서 BFS로 각 칸에 대한 최단 거리를 계산
   1. 아직 탑승하지 않은 고객의 위치를 순차적으로 탐색하여 가장 가까운 고객의 인덱스를 저장하고,
      가장 가까운 고객을 찾을 수 없을 경우, 택시가 도달할 수 없는 곳에 있다고 판단하여 즉시 종료
   2. 현재 남은 연료를 확인하여 고객의 위치까지 충분하다면 연료를 소비하여 이동하고, 아니라면 즉시 종료
5. 고객 위치까지 도착하고 BFS를 통해 현재 위치에서 각 칸에 대한 최단 거리를 계산
   1. 해당 고객의 인덱스로 목적지를 찾아 거리를 가져옴
      만약, BFS를 진행하며 목적지에 방문한 적이 없을 경우, 현재 위치에서 도달할 수 없는 곳에 있다고 판단하여 즉시 종료
   2. 현재 남은 연료를 확인하여 목적지까지 충분하다면 연료를 소비하여 이동하고 고객의 상태를 완료로 저장,
      아니라면 즉시 종료
   3. 소비한 연료의 2배를 현재 연료에 추가
6. 만약, 목적지까지 데려다 준 고객의 수가 M과 같은 경우 반복을 종료하고 남은 연료를 출력하고,
   아니라면 4번부터 다시 시작

03. 🛠️ 시도별 수정

1회차

• 택시가 고객이 있는 곳에 도달할 수 없는 경우를 고려하지 못 했음

2회차

• 택시가 고객의 목적지에 도달할 수 없는 경우를 고려하지 못 했음

3회차

---

04. 🗝️ 정답 코드

#include <bits/stdc++.h>
using namespace std;

template <typename T>
using matrix = vector<vector<T>>;

int N, M, fuel;

matrix<int> board;
matrix<int> dists;
matrix<bool> visited;

vector<pair<int, int>> customers;
vector<pair<int, int>> goals;
vector<bool> is_done;

const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

bool is_valid(int x, int y){ return (x > 0 && x <= N && y > 0 && y <= N); }

void mark_dists(pair<int, int> cur){
  queue<pair<int, int>> q;
  dists.assign(N + 1, vector<int>(N + 1, 0));
  visited.assign(N + 1, vector<bool>(N + 1, false));
  
  q.emplace(cur.first, cur.second);
  visited[cur.first][cur.second] = true;
  dists[cur.first][cur.second] = 0;

  while(!q.empty()){
    auto& [x, y] = q.front(); q.pop();

    for(int i = 0; i < 4; i++){
      int nx = x + dx[i], ny = y + dy[i];

      if(!is_valid(nx, ny) || board[nx][ny] == 1 || visited[nx][ny]) continue;

      q.emplace(nx, ny);
      visited[nx][ny] = true;
      dists[nx][ny] = dists[x][y] + 1;
    }
  }
}

int get_customer(){
  int near_idx = -1;

  for(int i = 0; i < customers.size(); i++){
    auto& [nx, ny] = customers[i];

    if(is_done[i] || !visited[nx][ny]) continue;
    else if(near_idx == -1) near_idx = i;
    else{
      auto& [x, y] = customers[near_idx];

      if(dists[x][y] > dists[nx][ny]) near_idx = i;
      else if(dists[x][y] == dists[nx][ny]){
        if(nx < x) near_idx = i;
        else if(nx == x && ny < y) near_idx = i;
      }
    }
  }

  return near_idx;
}

int solution(pair<int, int> taxi){
  int res = 0;

  while(res < M){
    mark_dists(taxi);
    int idx = get_customer();
    if(idx == -1) break;

    auto& [cx, cy] = customers[idx];
    auto& [gx, gy] = goals[idx];
    if(!visited[cx][cy]) break;
    else if((fuel - dists[cx][cy]) >= 0){
      taxi = customers[idx];
      fuel -= dists[cx][cy];
    } else break;
    
    mark_dists(taxi);
    if(!visited[gx][gy]) break;
    else if((fuel - dists[gx][gy]) >= 0){
      taxi = goals[idx];
      fuel += dists[gx][gy];
      is_done[idx] = true;

      res++;
    } else break;
  }

  return (res == M ? fuel : -1);
}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> N >> M >> fuel;
  board.resize(N + 1, vector<int>(N + 1));

  for(int i = 1; i <= N; i++)
    for(int j = 1; j <= N; j++) cin >> board[i][j];

  int x, y;
  cin >> x >> y;

  for(int i = 0; i < M; i++){
    int cx, cy, nx, ny;
    cin >> cx >> cy >> nx >> ny;

    customers.emplace_back(cx, cy);
    goals.emplace_back(nx, ny);
    is_done.push_back(false);
  }

  cout << solution({x, y}) << "\n";

  return 0;
}