백준 19238 스타트 택시 C++

 

https://www.acmicpc.net/problem/19238

19238번: 스타트 택시

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ19238.cpp

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

//
//  main.cpp
//  BJ19238
//
//  Created by 최화연 on 2022/04/24.
//

#include <iostream>
#include <queue>
using namespace std;

int N, M;
struct Texi {
    int r;
    int c;
    int fuel;
};
Texi texi;

struct Customer {
    int sr;
    int sc;
    int er;
    int ec;
    int s_dis;
};
struct cmp {
    bool operator() (Customer c1, Customer c2) {
        if (c1.s_dis == c2.s_dis) {
            if (c1.sr == c2.sr) {
                return c1.sc > c2.sc;
            }
            return c1.sr > c2.sr;
        }
        return c1.s_dis > c2.s_dis;
    }
};
Customer customer;
priority_queue<Customer, vector<Customer>, cmp> pq;

int map[21][21] = {0, };
int dr[4] = {0, -1, 0, 1};
int dc[4] = {-1, 0, 1, 0};

int get_dis_bfs(int sr, int sc, int er, int ec) {
    int visits[21][21] = {0, };
    queue<pair<pair<int, int>, int>> q;
    q.push({{sr, sc}, 0});
    visits[sr][sc] = 1;
    
    while (!q.empty()) {
        int r = q.front().first.first;
        int c = q.front().first.second;
        int dis = q.front().second;
        q.pop();
        if (r == er && c == ec) return dis;
        for (int d=0; d<4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (nr < 1 || nr > N || nc < 1 || nc > N) continue;
            if (visits[nr][nc] || map[nr][nc]) continue;
            visits[nr][nc] = 1;
            q.push({{nr, nc}, dis+1});
        }
    }
    
    return -1;
}

void start_texi() {
    while (!pq.empty()) {
        customer = pq.top();
        pq.pop();
        
        if (customer.s_dis > texi.fuel) {
            texi.fuel = -1;
            return;
        }
        
        texi.r = customer.sr;
        texi.c = customer.sc;
        texi.fuel -= customer.s_dis;
        
        int e_dis = get_dis_bfs(texi.r, texi.c, customer.er, customer.ec);
        if (e_dis == -1 || e_dis > texi.fuel) {
            texi.fuel = -1;
            return;
        }
        
        texi.fuel += e_dis;
        texi.r = customer.er;
        texi.c = customer.ec;
        
        priority_queue<Customer, vector<Customer>, cmp> new_pq;
        while (!pq.empty()) {
            customer = pq.top();
            pq.pop();
            customer.s_dis = get_dis_bfs(texi.r, texi.c, customer.sr, customer.sc);
            new_pq.push(customer);
        }
        pq = new_pq;
    }
}

int main(int argc, const char * argv[]) {
    cin >> N >> M >> texi.fuel;
    
    for (int r=1; r<=N; r++) {
        for (int c=1; c<=N; c++) {
            cin >> map[r][c];
        }
    }
    
    cin >> texi.r >> texi.c;
    
    for (int m=0; m<M; m++) {
        cin >> customer.sr >> customer.sc >> customer.er >> customer.ec;
        customer.s_dis = get_dis_bfs(texi.r, texi.c, customer.sr, customer.sc);
        if (customer.s_dis == -1) {
            cout << -1 << endl;
            return 0;
        }
        pq.push(customer);
    }
    
    start_texi();
    cout << texi.fuel << endl;

    return 0;
}

---

풀이 과정

풀이 시간 44분

#include <iostream>
#include <queue>
using namespace std;

int N, M;
struct Texi {
    int r;
    int c;
    int fuel;
};
Texi texi;

struct Customer {
    int sr;
    int sc;
    int er;
    int ec;
    int s_dis;
};
struct cmp {
    bool operator() (Customer c1, Customer c2) {
        if (c1.s_dis == c2.s_dis) {
            if (c1.sr == c2.sr) {
                return c1.sc > c2.sc;
            }
            return c1.sr > c2.sr;
        }
        return c1.s_dis > c2.s_dis;
    }
};
Customer customer;
priority_queue<Customer, vector<Customer>, cmp> pq;

int map[21][21] = {0, };
int dr[4] = {0, -1, 0, 1};
int dc[4] = {-1, 0, 1, 0};

int get_dis_bfs(int sr, int sc, int er, int ec) {
    int visits[21][21] = {0, };
    queue<pair<pair<int, int>, int>> q;
    q.push({{sr, sc}, 0});
    visits[sr][sc] = 1;
    
    while (!q.empty()) {
        int r = q.front().first.first;
        int c = q.front().first.second;
        int dis = q.front().second;
        q.pop();
        if (r == er && c == ec) return dis;
        for (int d=0; d<4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (nr < 1 || nr > N || nc < 1 || nc > N) continue;
            if (visits[nr][nc] || map[nr][nc]) continue;
            visits[nr][nc] = 1;
            q.push({{nr, nc}, dis+1});
        }
    }
    
    return -1;
}

void start_texi() {
    while (!pq.empty()) {
        customer = pq.top();
        pq.pop();
        
        if (customer.s_dis > texi.fuel) {
            texi.fuel = -1;
            return;
        }
        
        texi.r = customer.sr;
        texi.c = customer.sc;
        texi.fuel -= customer.s_dis;
        
        int e_dis = get_dis_bfs(texi.r, texi.c, customer.er, customer.ec);
        if (e_dis == -1 || e_dis > texi.fuel) {
            texi.fuel = -1;
            return;
        }
        
        texi.fuel += e_dis;
        texi.r = customer.er;
        texi.c = customer.ec;
        
        priority_queue<Customer, vector<Customer>, cmp> new_pq;
        while (!pq.empty()) {
            customer = pq.top();
            pq.pop();
            customer.s_dis = get_dis_bfs(texi.r, texi.c, customer.sr, customer.sc);
            new_pq.push(customer);
        }
        pq = new_pq;
    }
}

int main(int argc, const char * argv[]) {
    cin >> N >> M >> texi.fuel;
    
    for (int r=1; r<=N; r++) {
        for (int c=1; c<=N; c++) {
            cin >> map[r][c];
        }
    }
    
    cin >> texi.r >> texi.c;
    
    for (int m=0; m<M; m++) {
        cin >> customer.sr >> customer.sc >> customer.er >> customer.ec;
        customer.s_dis = get_dis_bfs(texi.r, texi.c, customer.sr, customer.sc);
        if (customer.s_dis == -1) {
            cout << -1 << endl;
            return 0;
        }
        pq.push(customer);
    }
    
    start_texi();
    cout << texi.fuel << endl;

    return 0;
}

---

이전 풀이

1.

풀이 시간 1시간 4분

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;

int N, M;
long long gas;
int area[22][22] = {0, };
int visit[22][22] = {0, };
int texi_x, texi_y;

struct Customer{
	//승객 번호
    int num;
    //출발지 위치
    int start_x;
    int start_y;
    //목적지 위치
    int dest_x;
    int dest_y;
    //승객의 출발지 위치와 택시와의 거리
    int dis = 0;
    //done = true -> 목적지에 도달함, done = false -> 아직 목적지에 도달하지 않음
    bool done = false;
};
struct cmp{
    bool operator()(Customer c1, Customer c2){
    	//출발지에서 택시와의 거리가 같은 경우,
        if(c1.dis == c2.dis){
        	//출발지의 행 번호가 같은 경우,
            if(c1.start_y == c2.start_y){
            	//출발지의 열 번호가 작은 순서대로 정렬
                return c1.start_x > c2.start_x;
            }
            //출발지의 행 번호가 작은 순서대로 정렬
            return c1.start_y > c2.start_y;
        }
        //출발지에서 택시와의 거리가 가까운 순서대로 정렬
        return c1.dis > c2.dis;
    }
};
Customer cus;
//승객 정보를 담는 배열
Customer customers[401];

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

//목적지까지 데려다 준 승객 수
int cnt = 0;

Customer find_customer(){
    priority_queue<Customer, vector<Customer>, cmp> pq;
    for(int i=0; i<M; i++){
    	//이미 목적지에 도달한 승객인 경우, 무시한다
        if(customers[i].done) continue;
        
        //목적지에 아직 도달하지 않은 승객의 출발지와 택시의 거리를 구한다
        cus = customers[i];
        memset(visit, 0, sizeof(visit));
        queue<pair<pair<int, int>, int>> q;
        //택시의 현재 위치에서 탐색 시작
        q.push({{texi_x, texi_y}, 0});
        visit[texi_y][texi_x] = 1;
        
        while(!q.empty()){
            int x = q.front().first.first;
            int y = q.front().first.second;
            int dis = q.front().second;
            q.pop();
            
            //출발지에 도달한 경우,
            if(x==cus.start_x && y==cus.start_y){
            	//택시와 출발지 사이의 거리를 설정하고, 우선순위 큐에 담는다
                cus.dis = dis;
                pq.push(cus);
                break;
            }
            
            for(int d=0; d<4; d++){
                int nx = x+dx[d];
                int ny = y+dy[d];
                //범위를 벗어난 경우, 무시한다
                if(nx<1 || nx>N || ny<1 || ny>N) continue;
                //벽이 있는 경우, 무시한다
                if(area[ny][nx]) continue;
                //이미 방문한 위치인 경우, 무시한다
                if(visit[ny][nx]) continue;
                
                visit[ny][nx] = 1;
                q.push({{nx, ny}, dis+1});
            }
        }
    }
    //태울 승객이 없는 경우, 승객 번호를 -1로 하여 return한다
    if(pq.empty()){
        cus.num = -1;
        return cus;
    }
    //태울 승객이 있는 경우, 가장 우선순위가 큰 승객을 return한다
    return pq.top();
}

void start_texi(){
	//모든 승객을 도착지로 데려다 줄 때까지 while문 반복
    while(cnt < M){
    	//1. 현재 택시 위치에서 최단 거리가 가장 짧은 승객을 고른다
        cus = find_customer();
        
        //승객이 없는 경우, 승객을 목적지로 데려다 주지 못하기 때문에 while문을 종료한다
        //ex) 벽에 둘러싸여 있어 도달할 수 있는 승객이 없는 경우
        if(cus.num == -1){
            gas = -1;
            break;
        }
        
        //2. 손님 태우러 이동
        //택시에서 승객의 위치까지 사용되는 연료를 뺀다
        gas -= cus.dis;
        
        //승객을 태우러 가다가 연료가 바닥난 경우, 승객을 목적지에 데려다주지 못하므로 while문을 종료한다
        if(gas < 0){
            gas = -1;
            break;
        }
        //승객을 태울 수 있는 경우, 택시 위치를 승객의 위치로 바꿔준다
        texi_x = cus.start_x;
        texi_y = cus.start_y;
        
        //3. 목적지로 이동
        memset(visit, 0, sizeof(visit));
        queue<pair<pair<int, int>, int>> q;
        q.push({{texi_x, texi_y}, 0});
        visit[texi_y][texi_x] = 1;
        
        //출발지에서 목적지까지의 거리
        int dest_dis = 0;
        while(!q.empty()){
            int x = q.front().first.first;
            int y = q.front().first.second;
            int dis = q.front().second;
            q.pop();
            //목적지에 도달한 경우
            if(x==cus.dest_x && y==cus.dest_y){
            	//출발지에서 목적지까지 사용되는 연료를 뺀다
                gas -= dis;
                dest_dis = dis;
                texi_x = x;
                texi_y = y;
                //승객을 목적지로 데려다줬으므로 done 처리한다
                customers[cus.num].done = true;
                break;
            }
            for(int d=0; d<4; d++){
                int nx = x+dx[d];
                int ny = y+dy[d];
                if(nx<1 || nx>N || ny<1 || ny>N) continue;
                if(area[ny][nx]) continue;
                if(visit[ny][nx]) continue;
                visit[ny][nx] = 1;
                q.push({{nx, ny}, dis+1});
            }
        }
        
        //dest_dis == 0 -> 벽에 둘러싸여 있어 목적지에 도달하지 못한 경우, 승객을 목적지까지 데려다주지 못하므로 while문을 종료한다
        //gas < 0 -> 목적지까지 이동하면서 연료가 바닥난 경우, 승객을 목적지까지 데려다주지 못하므로 while문을 종료한다
        if(dest_dis == 0 || gas < 0){
            gas = -1;
            break;
        }
        
        //목적지까지 데려다 준 승객 수 카운팅
        cnt++;
        //출발지에서 목적지까지 사용한 연료의 2배를 충전한다
        gas += (2*dest_dis);
    }
}

int main(int argc, const char * argv[]) {
    cin >> N >> M >> gas;
    for(int y=1; y<=N; y++){
        for(int x=1; x<=N; x++){
            cin >> area[y][x];
        }
    }
    cin >> texi_y >> texi_x;
    for(int i=0; i<M; i++){
        cin >> cus.start_y >> cus.start_x >> cus.dest_y >> cus.dest_x;
        cus.num = i;
        customers[i] = cus;
    }
    
    start_texi();
    cout << gas << endl;
    
    return 0;
}
//시간복잡도 = O(M^2logM * N^2) = O(M^3logM), 공간복잡도 = O(M)

---

2.

풀이 시간 1시간 17분

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;

int N, M, gas;
int area[21][21] = {0, };
int visit[21][21] = {0, };
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

//현재 택시 위치
int texi_x, texi_y;

struct Customer{
	//승객의 출발지
    int start_x;
    int start_y;
    //승객의 목적지
    int dest_x;
    int dest_y;
   	//승객과 택시 사이의 거리
    int dist_texi;
    //승객의 출발지와 목적지 사이의 거리
    int dist_dest;
};
Customer customer;
struct cmp{
    bool operator()(Customer c1, Customer c2){
    	//택시와의 최단거리가 같은 경우, 출발지의 행의 값이 작은 승객을 앞에 정렬
        if(c1.dist_texi == c2.dist_texi){
        	//출발지의 행의 값이 같은 경우, 출발지의 열의 값이 작은 승객을 앞에 정렬
            if(c1.start_y == c2.start_y){
                return c1.start_x > c2.start_x;
            }
            return c1.start_y > c2.start_y;
        }
        //택시와의 최단거리가 작은 승객을 앞에 정렬
        return c1.dist_texi > c2.dist_texi;
    }
};

priority_queue<Customer, vector<Customer>, cmp> customers;

//start에서 dest까지의 최단 거리를 구하는 함수
int get_dist(int start_x, int start_y, int dest_x, int dest_y){
    int dist = -1;
    //visit 배열 초기화
    memset(visit, 0, sizeof(visit));
    //출발지 방문 처리
    visit[start_y][start_x] = 1;
    //{{x, y}, 이동 거리}를 담는 큐
    queue<pair<pair<int, int>, int>> q;
    //출발지 위치와 이동 거리 0을 시작 노드로 큐에 push
    q.push(make_pair(make_pair(start_x, start_y), 0));
    while(!q.empty()){
        int now_x = q.front().first.first;
        int now_y = q.front().first.second;
        int now_dist = q.front().second;
        q.pop();
        //현재 위치가 도착지인 경우, 현재 이동 거리가 최단 거리이다
        if(now_y == dest_y && now_x == dest_x){
            dist = now_dist;
            break;
        }
        //상하좌우 인접한 위치 탐색
        for(int d=0; d<4; d++){
            int nx = now_x + dx[d];
            int ny = now_y + dy[d];
            //지도 범위를 벗어난 경우, 무시한다
            if(nx<1 || nx>N || ny<1 || ny>N) continue;
            //이미 방문한 곳인 경우, 무시한다
            if(visit[ny][nx] == 1) continue;
            //벽인 경우, 무시한다
            if(area[ny][nx] == 1) continue;
           	//빈 칸인 경우, {해당 위치, 이동거리 + 1}을 큐에 push하고 방문처리 한다
            q.push({{nx, ny}, now_dist+1});
            visit[ny][nx] = 1;
        }
    }
    return dist;
}


int main(int argc, const char * argv[]) {
    cin >> N >> M >> gas;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            cin >> area[i][j];
        }
    }
    cin >> texi_y >> texi_x;
    
    //O(M*(V+E)*log2 M)
    bool check = true;
    for(int i=0; i<M; i++){
        cin >> customer.start_y >> customer.start_x >> customer.dest_y >> customer.dest_x;
       	
        //승객 정보를 입력으로 받아올 때, 해당 승객과 택시 사이의 거리나 해당 승객의 출발지에서 목적지까지의 거리를 구한다
        customer.dist_texi = get_dist(texi_x, texi_y, customer.start_x, customer.start_y);
        customer.dist_dest = get_dist(customer.start_x, customer.start_y, customer.dest_x, customer.dest_y);
        
        //만약, 승객과 택시 사이의 거리가 -1이거나,출발지에서 목적지 사이의 거리가 -1인 경우,
    	//벽으로 막혀있어서 해당 승객은 목적지까지 갈 수 없는 경우를 의미 -> check = false
        if(customer.dist_texi == -1 || customer.dist_dest == -1){
            check = false;
            continue;
        }
        //그렇지 않은 경우, customers 우선순위 큐에 해당 승객을 push한다
        customers.push(customer);
    }
    
    //check = false인 경우, 승객을 목적지까지 데려다 줄 수 없는 경우가 있으므로 -1 출력
    if(!check){
        cout << -1 << endl;
        return 0;
    }

	//M명의 승객을 목적지까지 데려다준다 -> O(M^2*log2 M*(V+E)) = O(M^3*log2 M)
    while(!customers.empty()){
        //1. 승객 태우기
        customer = customers.top();
        customers.pop();
        //현재 승객의 출발지로 택시를 이동시킨다 -> 연료가 dist_texi만큼 소요
        texi_x = customer.start_x;
        texi_y = customer.start_y;
        gas -= customer.dist_texi;
        //만약, 연료가 남지 않은 경우, 해당 승객을 목적지까지 데려다 줄 수 없으므로 gas = -1로 바꾸고 while문을 벗어난다
        if(gas <= 0){
            gas = -1;
            break;
        }
        
        //2. 목적지로 가기
        //현재 승객의 목적지로 택시를 이동시킨다 -> 연료가 dist_dest만큼 소요
        texi_x = customer.dest_x;
        texi_y = customer.dest_y;
        gas -= customer.dist_dest;
        
        //주의: 목적지에 도달함과 동시에 연료가 바닥난 경우는 실패가 아니다라는 예외를 처리한다
        //연료가 음수인 경우에만 실패
        if(gas < 0){
            gas = -1;
            break;
        }
        //목적지에 도달하였으므로, dist_dest의 2배만큼 연료가 충전된다
        gas += (2*customer.dist_dest);
        
        //3. 승객 우선순위 재정렬 - 택시 위치가 바뀌었으므로 다음 승객을 찾기 위해 우선순위를 재정렬한다
        priority_queue<Customer, vector<Customer>, cmp> copy_customers;
        while(!customers.empty()){
            customer = customers.top();
            customers.pop();
            //승객과 택시 사이의 거리를 구하여 copy_customers 우선순위 큐에 push한다
            customer.dist_texi = get_dist(texi_x, texi_y, customer.start_x, customer.start_y);
            copy_customers.push(customer);
        }
        //새롭게 정렬된 승객이 담긴 copy_customers로 customers를 갱신한다
        customers = copy_customers;
    }
    cout << gas << endl;
    return 0;
}
//시간복잡도 = O(M^3*log2 M)