[백준] 19238번 스타트택시

19238 스타트택시

문제

---

스타트링크가 "스타트 택시"라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다.

택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있다. 알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다.

M명의 승객은 빈칸 중 하나에 서 있으며, 다른 빈칸 중 하나로 이동하려고 한다. 여러 승객이 같이 탑승하는 경우는 없다. 따라서 백준은 한 승객을 태워 목적지로 이동시키는 일을 M번 반복해야 한다. 각 승객은 스스로 움직이지 않으며, 출발지에서만 택시에 탈 수 있고, 목적지에서만 택시에서 내릴 수 있다.

백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다. 연료는 한 칸 이동할 때마다 1만큼 소모된다. 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료 양의 두 배가 충전된다. 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그 날의 업무가 끝난다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.

모든 승객을 성공적으로 데려다줄 수 있는지 알아내고, 데려다줄 수 있을 경우 최종적으로 남는 연료의 양을 출력하는 프로그램을 작성하시오.

입력

---

첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다.

다음 줄부터 N개의 줄에 걸쳐 백준이 활동할 영역의 지도가 주어진다. 0은 빈칸, 1은 벽을 나타낸다.

다음 줄에는 백준이 운전을 시작하는 칸의 행 번호와 열 번호가 주어진다. 행과 열 번호는 1 이상 N 이하의 자연수이고, 운전을 시작하는 칸은 빈칸이다.

그다음 줄부터 M개의 줄에 걸쳐 각 승객의 출발지의 행과 열 번호, 그리고 목적지의 행과 열 번호가 주어진다. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.

출력

---

모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양을 출력한다. 단, 이동 도중에 연료가 바닥나서 다음 출발지나 목적지로 이동할 수 없으면 -1을 출력한다. 모든 손님을 이동시킬 수 없는 경우에도 -1을 출력한다.

---

풀이)

bfs를 이용해서 푼 문제이다.

손님의 출발위치와 목적지위치를 저장하는 것이 중요하다.

그러므로

각 손님마다 1보다 큰 숫자 번호를 붙여 처음 출발하는 위치를 map에 표시해놨다. 

(즉 손님이 3명이라면 번호를 2,3,4라고 붙여서 map에 표시

 0은 빈 칸이고, 1은 벽이기 때문에)

또한, 손님의 목적지는 손님의 번호와 대칭되게 배열(destination[])에 저장해주었다. 

vector<pair<int,int>> destination

first값은 y값, second값은 x값

destination[2] = 2번 손님의 목적지

destination[3] = 3번 손님의 목적지

... 이런식으로

위의 저장한 값을 이용한 전반적인 풀이과정을 이러하다.

손님 수 M번 만큼 2개의 bfs함수를 수행한다.

1. 현재 택시 위치에서 가장 가까운 손님의 위치를 찾는 bfs함수(find_customer())

    (손님의 위치, 손님의 번호를 찾는다.)

    -> 손님의 위치를 발견못하면 fail    

2. 손님이 목적지까지 도달하게 하는 bfs함수(delivery())

   -> 손님을 목적지까지 태우지 못하면 fail

주의할점

1. A승객의 목적지와 B승객의 출발지가 같을 수 있다는 점(택시가 연료를 안들이고, 바로 손님을 찾을 수 있다)

2. 택시가 승객을 찾은 후, 승객을 목적지까지 데려가지 못할 수도 있다는 점(연료가 부족하거나, 벽에 막혀서)

코드)

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int N, M, K;//지도 영역,손님, 초기연료
int map[21][21];//행과 열 번호는 1이상 N이하이므로 21까지
bool visited[21][21];
pair<int, int> taxi;//택시의위치
vector<pair<int, int>> destination;//손님의 목적지를 저장
int customer = 2;//손님 번호(map의 0은 빈칸, 1은 벽이니깐 2번부터 표시)
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int des_num = 0;//택시가 태운 손님의 번호
int result = 0;//목적지까지 데러다준 승객
 
 
//가장 가까운 손님의 위치를 찾아 return하는 함수
pair<int, int> find_customer() {
    queue<pair<int, int>> qu;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            visited[i][j] = false;
        }
    }
    if (map[taxi.first][taxi.second] >= 2) { // 택시출발지가 바로 다른손님의 출발지였다면
        des_num = map[taxi.first][taxi.second];
        return { taxi.first,taxi.second };
    } 
    qu.push({ taxi.first,taxi.second });
    visited[taxi.first][taxi.second] = true;
    vector<pair<pair<int,int>,int>> temp;//손님 번호와 위치 저장
    bool finish = false;
    while (!qu.empty()&&K>=0&&finish==false) {
        int size = qu.size();
        while (size--) {
            int y = qu.front().first;
            int x = qu.front().second;
            qu.pop();
            for (int i = 0; i < 4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];
                if (ny<1 || ny>N || nx<1 || nx>N)continue;//범위밖
                if (visited[ny][nx]||map[ny][nx]== 1) continue;//이미 방문 or 벽
                if (map[ny][nx] >= 2) {
                    temp.push_back({{ny,nx} ,map[ny][nx] });
                    finish = true; //손님을 찾은 거리와 동일한 거리에 있는 다른 손님들만 찾기 위해 이용
                } 
                visited[ny][nx] = true;
                qu.push({ ny,nx });
                
            }
        }
        K--;
    }
    
    if (temp.size() >= 1) {//가장 가까운 거리에 있는 손님들을 찾음
        if(temp.size()>1)sort(temp.begin(), temp.end());//여러명일경우, 행번호가 작은 승객, 열 번호가 작은 승객
        des_num = temp[0].second;
        return { temp[0].first.first,temp[0].first.second };
    }
    else return { -1,-1 };
}
 
bool delivery() {
    queue<pair<int, int>> qu;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            visited[i][j] = false;
        }
    }
    qu.push({ taxi.first,taxi.second });
    visited[taxi.first][taxi.second] = true;
    int first = K;//목적지 가기 전 택시가 가진 초기 연료
 
    while (!qu.empty() && K >= 0) {
        int size = qu.size();
        while (size--) {
            int y = qu.front().first;
            int x = qu.front().second;
            qu.pop();
            for (int i = 0; i < 4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];
                if (ny<1 || ny>N || nx<1 || nx>N)continue;//범위밖
                if (visited[ny][nx] || map[ny][nx] == 1) continue;//이미 방문 or 벽
                if (ny == destination[des_num].first && nx == destination[des_num].second) {
                    K--;
                    if (K < 0) return false; //도착했는데 연료를 다 쓴 상태이면 실패
                    K += (first - K) * 2;//소모한 연료의 두 배 충전
                    taxi.first = ny;//택시 위치 목적지로 초기화
                    taxi.second = nx;
                    return true;
                }
                visited[ny][nx] = true;
                qu.push({ ny,nx });
 
            }
        }
        K--;
    }
    return false;
}
 
 
int main() {
 
    scanf("%d %d %d", &N, &M, &K);
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            scanf("%d", &map[i][j]);//0은 빈칸, 1은 벽
        }
    }
    scanf("%d %d", &taxi.first, &taxi.second);
    int sy, sx, dy, dx;//손님의 출발지 행과 열, 목적지 행과 열
    destination.resize(M + 2);//손님 번호 2번부터 시작하므로
    for (int i = 0; i < M; i++) {
        scanf("%d %d %d %d", &sy, &sx, &dy, &dx);
        map[sy][sx] = customer;//map에 손님 초기 위치 표시
        destination[customer].first = dy;
        destination[customer].second = dx;
        customer++;
    }
    //손님 수 M 만큼만 수행하면 된다.
    for (int i = 0; i < M; i++) {
        //1.가장 가까운 손님 번호 찾기
        pair<int, int> c = find_customer();
        if (c.first == -1) break;//만약 연료가 부족해서 손님을 못태운 경우
 
        taxi.first = c.first;//택시의 위치 손님의 위치로 초기화
        taxi.second = c.second;
        map[c.first][c.second] = 0;//손님이 있던 자리 빈칸으로 초기화->나중에 다시 계산할 일 없게
 
        //2.손님의 목적지까지 데려다 주기
        bool check = delivery();
 
        if (K < 0 || check == false) break;//만약 연료가 부족하거나, 벽에 막혀서 손님을 목적지까지 못데려간 경우
        result++;
    }
    
    if (result == M) printf("%d", K);
    else printf("-1");
    return 0;
}