스타트 택시

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
// 0210 ~ 0417
int N,M,oil,ans;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int board[22][22];
int cost[22][22];
pair<int,int> driver;
struct client{
    int stR;
    int stC;
    int destR;
    int destC;
    bool end = false;
};
vector<client> client_v;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

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

    cin >> driver.first >> driver.second;
    for(int i=1;i<=M;i++)
    {
        int s1, s2, e1, e2;
        cin >> s1 >> s2 >> e1 >> e2;
        client c;
        c.stR = s1; c.stC = s2;
        c.destR = e1; c.destC = e2;
        client_v.push_back(c);
        board[s1][s2] = i+1; // 1번손님 --> 2로 표기
    }
    int size = M;
    while(size--)
    {
        /* cost 초기화 */
        for(int i=1;i<=N;i++)
            fill(cost[i]+1, cost[i]+N+1, -1);
        /* 현재 Driver에서 가장 가까운 고객 탐색 */
        client findClient; findClient.stR = 1e9; findClient.stC = 1e9;
        int need_cost = 0;
        queue<pair<int,int>> q;
        cost[driver.first][driver.second] = 0;
        q.push(driver);
        int preAns = ans;
        /* 드라이버 위치에 바로 손님이 있으면! */
        if(board[driver.first][driver.second] >= 2){
            int num = board[driver.first][driver.second];
            findClient.stR = driver.first;
            findClient.stC = driver.second;
            ans++;
            goto findDest;
        } 
        while(q.size() > 0)
        {
            int len = q.size();
            bool END = false;
            while(len--)
            {
                auto cur = q.front(); q.pop();
                for(int dir=0;dir<4;dir++)
                {
                    int ny = cur.first + dy[dir];
                    int nx = cur.second + dx[dir];
                    if(nx<1 or ny<1 or nx>N or ny>N) continue;
                    if(board[ny][nx] == 1 or cost[ny][nx] >= 0) continue;
                    q.push({ny,nx});
                    cost[ny][nx] = cost[cur.first][cur.second] + 1;
                    if(board[ny][nx] >= 2){
                        if(findClient.stR > ny){
                            findClient.stR = ny;
                            findClient.stC = nx;
                            driver.first = ny;
                            driver.second = nx;
                        }else if(findClient.stR == ny and findClient.stC > nx){
                            findClient.stR = ny;
                            findClient.stC = nx;
                            driver.first = ny;
                            driver.second = nx;
                        }
                        END = true;
                    }
                }
            }
            if(END == true){
                need_cost = cost[findClient.stR][findClient.stC];
                ans++;
                break;
            }
        }
        findDest:;
        /* 손님을 찾지 못하면 종료 */
        if(ans == preAns){
            oil = -1;
            break;
        }
        /* 가는데 연료가 부족하면 종료 */
        if(need_cost > oil) {
            oil = -1;
            break;
        }
        oil -= need_cost;
        /* 고객의 출발지 -> 고객의 목적지 */
        /* cost 초기화 */
        for(int i=1;i<=N;i++)
            fill(cost[i]+1, cost[i]+N+1, -1);
        queue<pair<int,int>> q2;
        pair<int,int> dest = {client_v[board[findClient.stR][findClient.stC]-2].destR, client_v[board[findClient.stR][findClient.stC]-2].destC};
        board[findClient.stR][findClient.stC] = 0; // board판 삭제
        /* 출발지가 목적지이면 바로 pass */
        if(dest.first == driver.first and dest.second == driver.second){
            ans++;
            continue;
        }
        cost[findClient.stR][findClient.stC] = 0;
        q2.push({findClient.stR, findClient.stC});
        bool success = false;
        while(!q2.empty())
        {
            auto cur = q2.front(); q2.pop();
            for(int dir=0;dir<4;dir++)
            {   
                int ny = cur.first + dy[dir];
                int nx = cur.second + dx[dir];
                if(nx<1 or ny<1 or nx>N or ny>N) continue;
                if(board[ny][nx] == 1 or cost[ny][nx] >= 0) continue;
                q2.push({ny,nx});
                cost[ny][nx] = cost[cur.first][cur.second] + 1;
                if(ny == dest.first and nx == dest.second){
                    oil -= cost[ny][nx];
                    if(oil < 0) {
                        success = false;
                    }else{
                        oil += cost[ny][nx]*2;
                        driver.first = ny;
                        driver.second = nx;
                        success = true;
                    }
                    goto stop;
                }
            }
        }
        stop:;
        if(success == false){
            oil = -1;
            break;
        }
    }
    cout << oil;
    return 0;
}

• 주의
  • board[][]와 cost[][]를 인덱스 1~N까지 사용하는데 초기화를 0부터 함
    --> 아래처럼 해야 1부터 N까지 초기화가 된다
    for(int i=1;i<=N;i++) fill(cost[i]+1, cost[i]+N+1, -1);
  • 예외처리
    • 고객을 태우러 갈 때 연료가 부족하면 out
    • 목적지에 갈 때 연료가 부족하면 out
    • 현재 택시 위치에 손님이 있는 경우 --> 바로 승차
    • 현재 택시 위치에 목적지가 있는 경우 --> 바로 하차

• 느낀 것
  • 같은 최단 거리 중 행과 열이 가장 작은 곳을 찾기 위해서 동일한 거리마다 BFS를 수행하기 위해 q의 size를 이용하면 된다 (while(size--))