[백준] 19238 스타트 택시 (C++)

백준 19238 스타트 택시

1. 문제

문제 링크

2. 접근법

[ 문제 접근 ]

 

삼성 SW 역량테스트에 출제된 시뮬레이션 문제이다.

풀다가 시간 초과가 나서 다른 블로그를 참고해서 풀었다.

 

* 택시가 태울 승객을 고를 때 현재 위치에서 최단거리가 짧은 승객을 골라야 하는데 그런 승객이 여러 명인 경우 행 번호가 작은 승객을 고르고 행 번호도 같다면 열 번호가 작은 승객을 고른다.

-> 승객을 고를때 최단거리가 같은 승객의 행, 열 좌표를 알아야 하므로 pNum을 사용하여 인덱스를 저장시켜 주었다. 또한 선택된 승객의 인덱스를 가지고 택시의 도착 좌표를 업데이트시켜주고, 남은 연료로 승객의 도착지까지 운전할 수 있는지의 여부를 판별하였다.

3. 코드

#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int mini = 987654321;
int n, m, oil, answer;
int taxi_r, taxi_c;
bool checked[21][21];
int map[21][21];
int pNum;
struct Passenger
{
    int start_r, start_c;
    int end_r, end_c;
    bool complete;
};
struct Taxi
{
    int r, c, dis;
};
int dr[4] = { -1, 1, 0, 0 };
int dc[4] = { 0, 0, -1, 1 };
Passenger pass[450];
//손님까지의 최단거리 찾기
int findMinDistance(int passR, int passC)
{
    memset(checked, false, sizeof(checked));
    queue<Taxi> tQ;
    tQ.push({ taxi_r, taxi_c, 0 });
    checked[taxi_r][taxi_c] = true;
    while (!tQ.empty())
    {
        int row = tQ.front().r;
        int col = tQ.front().c;
        int dis = tQ.front().dis;
        tQ.pop();
        if (row == passR && col == passC)
            return dis;
        for (int i = 0; i < 4; ++i)
        {
            int nr = row + dr[i];
            int nc = col + dc[i];
            if (nr <= 0 || nr > n || nc <= 0 || nc > n)
                continue;
            if (map[nr][nc] != 1 && !checked[nr][nc])
            {
                checked[nr][nc] = true;
                tQ.push({ nr, nc, dis + 1 });
            }
        }
    }
    return -1;
}
//가장 가까운 승객 찾기
void findMinPassenger()
{
    mini = 987654321;
    for (int i = 0; i < m; ++i)
    {
        if (pass[i].complete)
            continue;
        int sr = pass[i].start_r;
        int sc = pass[i].start_c;
        int d = findMinDistance(sr, sc);
        if (d == -1)
            continue;
        if (mini > d)
        {
            mini = d;
            //승객의 위치가 같은 경우에 체크하기위해 pNum 업데이트 시킴
            pNum = i;
        }
        //승객의 위치가 같은 경우
        else if (mini == d)
        {
            //행이 같은 경우에 열의 위치 확인
            if (pass[i].start_r == pass[pNum].start_r)
            {
                //pNum의 열이 더 크다면 i를 선택함
                if (pass[i].start_c < pass[pNum].start_c)
                    pNum = i;
            }
            //행이 같지 않다면 더 작은 행의 인덱스를 선택함
            else if (pass[i].start_r < pass[pNum].start_r)
                pNum = i;
        }
    }
}
//손님들의 도착여부 판별
bool End()
{
    for (int i = 0; i < m; ++i)
    {
        if (!pass[i].complete)
            return false;
    }
    return true;
}
//남은 연료로 도착지까지 손님을 데려올 수 있는지 판별
bool isPossible(int idx)
{
    int d = findMinDistance(pass[idx].end_r, pass[idx].end_c);
    if (d == -1)
        return false;
    oil -= d;
    if (oil < 0)
        return false;
    pass[idx].complete = true;
    oil += d * 2;
    return true;
}
int main()
{
    ios_base::sync_with_stdio(false);
    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 >> map[i][j];
        }
    }
    cin >> taxi_r >> taxi_c;
    //손님들의 위치 담아줌
    for (int i = 0; i < m; ++i)
    {
        cin >> pass[i].start_r >> pass[i].start_c >> 
            pass[i].end_r >> pass[i].end_c;
        pass[i].complete = false;
    }
    //손님들이 도착지까지 도착하지 않은 경우에 반복함
    while (!End())
    {
        //손님까지의 최단거리 찾기
        findMinPassenger();
        //찾은 뒤 택시의 출발위치와 남은 연료 업데이트
        taxi_r = pass[pNum].start_r;
        taxi_c = pass[pNum].start_c;
        oil -= mini;
        //남은 연료로 도착지까지 손님을 데려올 수 있는지 판별
        if (!isPossible(pNum))
        {
            //데려올 수 없다면 -1로 업데이트 시킨 후 바로 종료
            oil = -1;
            break;
        }
        //택시 위치를 승객의 도착지로 업데이트
        taxi_r = pass[pNum].end_r;
        taxi_c = pass[pNum].end_c;
    }
    //남은 연료 리턴
    cout << oil << "\n";
    return 0;
}

4. 결과