32. [백준 19238번 / C++] 스타트 택시

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

19238번: 스타트 택시

 

어른 상어에서 강제 레벨업을 한건지 강하게 데인건지 알 수가 없지만 굉장히 빨리 푼 문제다.

 

문제의 내용은 정말 간단한데 택시가 주어진 연료 안에 '모든 승객을 태울 수 있는가'를 판단한다.

 

문제 조건은 다음과 같다.

1. 연료 안에서만 이동할 수 있다.
2. 문제에서 주어진 조건의 순서대로 승객을 태운다.
3. 승객을 태운 후! 그 다음 목적지까지 이동하면서 사용한 연료를 목적지로 이동이 가능하다면 2배로 돌려준다.
4. 모든 이동은 '최단 거리'로 이루어진다.

일단 4번 조건인 '최단거리'에 집중하자. 사실 최단거리를 구하는 방법은 워낙 많지만 이렇게 같은 가중치에 대해서 2차원 배열에서의 최단거리는 난 보통 BFS를 사용한다.

 

즉, 단순히 구현해야하는 것은 다음의 순서다.

1. 현재 택시 위치에 대해 모든 공간에 대한 '최단거리'를 계산한다. (BFS 사용)
2. 승객을 문제에서 주어진대로 정렬한다.
3. 정렬된 승객을 기준으로 가장 먼저 태워야하는 승객을 태운다. 이 과정에서 연료가 사용된다. 연료가 승객까지 가는 거리에 비해 부족하다면 '실패'다.
4. 승객을 태운 위치가 택시의 새로운 위치가 되기 때문에 1번을 반복해서 최단거리를 계산한다.
5. 승객의 목적지로 이동한다. 이 과정에서 연료가 사용된다. 도착에 성공할 경우 연료를 두배로 돌려받고 연료가 부족하다면 '실패'다.
6. 과정을 마치고 모든 승객을 태웠는지 체크한다. 모두 태웠다면 종료하고 남은 연료를 반환한다.
7. 1 ~ 6을 반복한다.

여기까지 구현하고 제출하면! 아마 바로 실패할 것이다. 왜 그럴까?

 

사실 문제의 함정은 '모든 승객을 태울 수 있는가'이다. 얼핏 보면 그냥 목적지까지 데려다 줄 수 있는가 싶지만, 그냥 승객 자체를 못태우는 경우가 있는 것이다. 바로 벽에 막힌 경우를 말한다.

 

문제는 벽에 막혀서 가지 못하는 경우 BFS를 사용한 최단거리 계산에서 문제가 발생하기 때문에 이에 대한 다른 장치를 둬야한다.

 

바로 코드를 보자.

 

#include<bits/stdc++.h>
using namespace std;
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
int n, m, k, a[21][21], visited[21][21], sy, sx, y, x;
pair<int, int> arrive[404];
struct B{
	int num, py, px;
};
vector<B> person;

bool cmp(B a, B b){
	if(visited[a.py][a.px] == visited[b.py][b.px]){
		if(a.py == b.py) return a.px < b.px;
		else return a.py < b.py;
	}else return visited[a.py][a.px] < visited[b.py][b.px];
}
void shortCut(){
	memset(visited, 0, sizeof(visited));
	queue<pair<int, int>> q;
	visited[sy][sx] = 1;
	q.push({sy, sx});
	
	while(q.size()){
		tie(y, x) = q.front();
		q.pop();
		for(int i = 0; i < 4; i++){
			int ny = y + dy[i];
			int nx = x + dx[i];
			if(ny < 0 || ny >= n || nx < 0 || nx >= n || a[ny][nx] == 1 || visited[ny][nx]) continue;
			visited[ny][nx] = visited[y][x] + 1;
			q.push({ny, nx});
		}
	}
}
	// 현재 택시로부터 모든 거리 찾기 
	// -> person정렬 후, 첫번째 사람에게 이동( 항상 연료 확인 ) 
	// -> 목적지까지 이동할 수 있는가 확인 후 이동할 수 있다면 연료 충전.
	// -> 반복하기전에 모든 승객을 태웠는가 확인. 
void solve(){
	shortCut();
	sort(person.begin(), person.end(), cmp);	
	
	if(k >= visited[person[0].py][person[0].px] - 1 && visited[person[0].py][person[0].px] != 0){ // 승객에게 이동이 가능하다면 
		k -= (visited[person[0].py][person[0].px] - 1);
		sy = person[0].py;
		sx = person[0].px;
	}else{ // 연료가 부족하다면 그냥 실패로 바로 함수 종료. 
		cout << -1 << "\n";
		exit(0);
	}
	
	shortCut(); // 현재 위치에서 최단거리 다시.
	
	if((k >= visited[arrive[person[0].num].first][arrive[person[0].num].second] - 1) && visited[arrive[person[0].num].first][arrive[person[0].num].second] != 0){ // 목적지까지 갈 수 있다면 
		k -= visited[arrive[person[0].num].first][arrive[person[0].num].second] - 1;
		tie(sy, sx) = arrive[person[0].num];
		k += 2 * (visited[arrive[person[0].num].first][arrive[person[0].num].second] - 1);
		
		person.erase(person.begin(), person.begin() + 1);
	}else{
		cout << -1 << "\n";
		exit(0);
	}
}

int main(){
	cin >> n >> m >> k;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> a[i][j];
		}
	}
	cin >> sy >> sx;
	sy--; sx--;
	for(int i = 1; i <= m; i++){
		cin >> y >> x;
		y--; x--;
		person.push_back({i, y, x});
		
		cin >> y >> x;
		y--; x--;
		arrive[i] = {y, x};
	}
	int flag = 0;
	while(true){
		solve();
		if(person.size() == 0){
			flag = 1;
			break;
		}
	}
	if(flag) cout << k << "\n";
	
	return 0;	
}

 

승객을 태우러 가는 길, 승객을 목적지로 태워주는 길. 둘 모두에 대해서 연료가 부족하다면 exit을 이용해서 바로 함수를 종료하는 것을 확인할 수 있다. 이렇게하면 굳이 main함수의 while문안에서 별다른 로직없이 종료가 가능하다.

 

또한 visited[ ][ ]는 최단거리를 의미하는데 이 값이 0이라면 현재 택시 위치에서 이 곳으로 갈 수 없음을 의미하기 때문에 visited[ ][ ] != 0으로 갈 수 있는 경우만 판단한다.

 

그 이외는 앞서 설명한 로직을 그대로 구현한 것이다.