[백준/c++] 19238 스타트 택시

문제

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

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

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

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

<그림1>

 

<그림 1>은 택시가 활동할 영역의 지도를 나타내며, 택시와 세 명의 승객의 출발지와 목적지가 표시되어 있다. 택시의 현재 연료 양은 15이다. 현재 택시에서 각 손님까지의 최단거리는 각각 9, 6, 7이므로, 택시는 2번 승객의 출발지로 이동한다.

<그림 2>는 택시가 2번 승객의 출발지로 가는 경로를, <그림 3>은 2번 승객의 출발지에서 목적지로 가는 경로를 나타낸다. 목적지로 이동할 때까지 소비한 연료는 6이고, 이동하고 나서 12가 충전되므로 남은 연료의 양은 15이다. 이제 택시에서 각 손님까지의 최단거리는 둘 다 7이므로, 택시는 둘 중 행 번호가 더 작은 1번 승객의 출발지로 이동한다.

<그림 4>와 <그림 5>는 택시가 1번 승객을 태워 목적지로 이동시키는 경로를 나타낸다. 남은 연료의 양은 15 - 7 - 7 + 7×2 = 15이다.

모든 승객을 성공적으로 데려다줄 수 있는지 알아내고, 데려다줄 수 있을 경우 최종적으로 남는 연료의 양을 출력하는 프로그램을 작성하시오.<그림 6>과 <그림 7>은 택시가 3번 승객을 태워 목적지로 이동시키는 경로를 나타낸다. 최종적으로 남은 연료의 양은 15 - 5 - 4 + 4×2 = 14이다.

입력

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

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

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

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

출력

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

 

구현해야할 조건

 구현해야할 조건이 무수하게 많지만 차근차근 생각을 해보자. 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그날의 업무가 끝나게 된다! 택시는 최단경로로 상하좌우 네방향으로 빈칸 중 하나로 이동한다.

단, 여러 승객이 같이 탑승하는 경우는 없으며, 백준은 한 승객을 태워 목적지로 이동시키는 일을 M번 반복해야 한다.

현재 위치에서 최단거리가 가장 짧은 승객을 고르고, 그런 승객이 여러 명이면 y축을 기준 가장 작은 승객, 또 많다면, x축을 기준으로 가장 작은 승객을 태우는데, 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 거리는 0이다.

한칸 이동시 연료 1이 소모되고, 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료의 양의 두 배가 충전이 된다. 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그날의 업무가 끝이난다.(-1출력)

승객을 못태울 수 있는 경우도 존재한다!(개인적인 논리) 벽이 존재하므로 벽을 넘어서 이동하지 못하기 때문에, dist배열에는 0으로 표시되지만, visited배열에는 방문 흔적이 없기 때문에, 그쪽으로 이동하지 못한다. 그렇기 때문에 당연지사 -1을 출력을 바로 해야한다. 하지만, 전부다 방문해주었고 더이상의 손님이 없을 경우도 존재한다. 그럴때는 chk boolean을 사용해서 문제를 해결하자!

단, 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다( 도착과 동시에 0이라면 실패로 간주하지 않는다.)

!!새로운 방식으로 업데이트 했습니다!!

 

code

 

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>

#define MAX 21

using namespace std;

typedef struct{
	int num;
	int y;
	int x;
	int dist;
}Customer; // vector

typedef struct{
	int num; // 몇번째 손님인지는 파악을 해야한다.  
	int y;
	int x;
	int dest_y;
	int dest_x;
	bool chk; // 데려다 줬는지 확인해주기 
}Customer_2; 

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

int n,m,f; // n : boardsize, m : customer cnt, f : fuel
int taxi_x, taxi_y; // taxi_location

int board[MAX][MAX];
int temp_board[MAX][MAX];
bool visited[MAX][MAX];  

Customer_2 c[MAX*MAX]; // boarsize의 최대값으로 메모리 할당해주기 

bool comp(Customer &a, Customer &b){
	
	/*
	아까 설명했던, 어떤 손님 먼저 데려다주지? 
	
	*/
	
	if(a.dist == b.dist)
	{
		if(a.y == b.y)
			return a.x < b.x;
		return a.y < b.y;
	}
	return a.dist < b.dist;
}

void BFS()
{
	memset(temp_board,0,sizeof(temp_board)); // distance 저장 임시 배열 
	memset(visited,false,sizeof(visited)); // 방문했는지 확인 여기가 가장 중요 왜냐면 벽이 있기 때문에! 
	
	queue<pair<int,int> > q;
	q.push({taxi_y,taxi_x}); // 택시의 위치는 항상 변하니까 전역변수로 취해주고
	visited[taxi_y][taxi_x] = true; // 제자리는 이미 방문했으니까 0이 된다.
	
	while(!q.empty())
	{
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		
		for(int i = 0; i < 4; i++){
			int ny = y + dy[i];
			int nx = x + dx[i];
			
			if(0 <= nx && nx < n && 0 <= ny && ny < n){
				if(!visited[ny][nx] && board[ny][nx] == 0)
				{
					visited[ny][nx] = true;
					temp_board[ny][nx] = temp_board[y][x] + 1;
					q.push({ny,nx});
				}
			}
		}
	}
	return;
}

int main()
{
	cin >> n >> m >> f;
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> board[i][j]; // wall, empty chk array
		}
	}
	
	cin >> taxi_y >> taxi_x;
	taxi_y--; taxi_x--; // 배열을 전체적으로 1씩 뺏기 때문에 이점을 유의하자
	
	/*
	손님의 위치는 변함이 없다. 움직이지 않으니까 배열에 저장해주고, update해줄 필요도 없다. 	
	*/
	
	for(int i = 1; i <= m; i++){
		int y,x,dest_y,dest_x;
		cin >> y >> x >> dest_y >> dest_x; // 위의 택시의 위치 빼주듯이 이것도 마찬가지 
		
		c[i] = {i,y-1,x-1,dest_y-1,dest_x-1,false}; 
	}
	
	bool no_move = false; 
	
	while(1) // 전체 손님을 데려다 줘야 하니까 while문을 사용하자 
	{
		/*
		손님의 위치가 택시의 위치와 비교해서 어디에 위치하는지 파악해야한다.
		BFS()를 사용해서 손님의 위치를 뽑아내자 
		*/
		
		BFS();
		
		/*
		손님의 위치를 파악했으니, 먼저 태워야할 가장 가까운 손님을 파악하자
		거리가 같다면, y가 가장 작은, y마저 같다면 x가 가장 작은 
		*/
		
		vector<Customer> v;
		
		for(int i = 1; i <= m; i++){
			
			/*
			visited에 방문하지 않으면 절대 택시가 못간다는게 증명BFS()로!
			false라면 택시는 전체를 운송하지 못하기 때문에 -1을 반환한다. 
			첫번쨰 종료 사례 
			*/
			
			if(!visited[c[i].y][c[i].x]) 
			{
				cout << -1;
				return 0;  
			}
			
			/*
			손님 운송이 끝난 애들을 true로 바꿔주었기 때문에 continue; 
			*/
			
			if(c[i].chk == true)
				continue; 
			
			v.push_back({i,c[i].y,c[i].x,temp_board[c[i].y][c[i].x]});
		}
		
		/*
		손님 전체를 방문해줬다는 조건, 두번째 종료 사례 
		
		*/ 
		
		if(v.size() == 0)
			break;
		
		sort(v.begin(),v.end(),comp);
		
		/*
		정렬 후 v[0]번째 손님으로 fuel을 삭제시켜보자! 
		*/
		
		f -= v[0].dist; // 거리만큼 이동해서 태웠다?
		
		if(f < 0){
			no_move = true;
			break; // 연료가 다 떨어진 상황 종료조건 3번째 
		} 
		
		/*
		택시의 이동 
		*/
		taxi_x = v[0].x;
		taxi_y = v[0].y;
		
		BFS(); // 택시가 도착장소까지 얼마나 걸리는지 체크를 해줘야겠지?
		
		int dest_x = c[v[0].num].dest_x;
		int dest_y = c[v[0].num].dest_y; // 도착위치 확인
		
		f -= temp_board[dest_y][dest_x];
		
		if(f < 0){ 
			no_move = true;
			break; // 종료조건 3번쨰 0까지는 가능하다! 도착과 동시에 0이 된것 
		}
		
		f += (temp_board[dest_y][dest_x] * 2); // 2배의 연료 충전 
		
		c[v[0].num].chk = true; // 손님을 완벽히 데려다 줌 
		
		taxi_x = c[v[0].num].dest_x;
		taxi_y = c[v[0].num].dest_y; // 택시 위치 다시 update 
	}
	
	if(no_move)
		cout << -1;
	else
		cout << f;
	
	return 0;
}