[백준] 19238번: 스타트 택시

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

19238번: 스타트 택시

꼼꼼히 문제를 읽어야 하는 문제이다. 주의할 점이 상당히 많기 때문이다.

우선 주요한 수도 코드를 만들어보면 다음과 같다.

1. 후보 고객 탐색

- 최단 거리에 있어야 한다. → BFS 탐색

- 만약 최단 거리인 고객이 다수라면, 우선순위에 따라 정렬

- 보유 연료만으로 도달 불가능한 고객도 고려 → 바로 -1 리턴

 

2. 해당 고객을 목적지까지 모시는 데 필요한 연료를 파악

- 해당 고객의 목적지를 파악

- 목적지까지 도달하기 위해 필요한 연료를 파악

- 목적지까지 애초에 도달이 불가능한 케이스 존재

- 보유 연료만으로 도달 불가능한 케이스 존재

 

3. 남은 에너지 갱신, 배열 값 갱신

- 해당 고객을 재탐색하는 일이 없도록 제거(이미 처리 불가능한 고객도 제거해야한다는 점 잊지 않기)

 

추가 주의사항)

💡 고객들의 목적지는 겹칠 수 있다. 다행히도 나는 애초에 고객별 목적지를 배열에 입력하지 않고, 별도의 배열에 저장해둬 고객의 번호를 알면 바로 목적지를 알 수 있는 구조로 코드를 짰다. 물론 문제를 똑바로 읽진 않아서 문제이기는 하다.

💡 문제에 언급되지 않은 내용은 어림짐작하지 않아야한다는 교훈을 주는 문제이다.

 

이 문제에서는 고객과의 거리, 그리고 고객과 목적지까지의 거리는 모두 최단 거리이기를 요구하기 때문에 BFS(너비 우선 탐색)을 활용하면 문제를 풀 수 있다.

그리고 생각보다 고객의 정보를 2차원 배열에 어떻게 녹여낼지가 생각보다 관건이다.

물론 고객의 정보를 다른 2차원 배열을 쓴다면, 정보가 분리되어 깔끔하지만 메모리 초과가 우려되기 때문에 될 수 있으면 한 배열에 담을 수 있는 한 많은 정보를 담으려고 한다.

 

기존의 배열의 정보는 아래와 같다.

0 → 접근 가능한 칸

1 → 접근 불가능한 칸

 

여기에 나는 음수로 고객의 출발점을 기록했다.

-1 → 1번째 고객의 출발점

-2 → 2번째 고객의 출발점

....

 

목적지는 겹칠 수도 있고, 어차피 배열을 통해 도착점을 탐색할 필요는 없고 고정된 값으로만 필요하다.

그래서 고객의 번호만 알면 별도의 배열을 통해 접근할 수 있도록 했다. 

그리고 출발점 → 도착점까지의 BFS를 수행한다.

 

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

using namespace std;
int n, m;
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};

bool cmp(pair<pair<int,int>, int> &a, pair<pair<int,int>, int> &b) {
	if(a.first.first  == b.first.first) {
		return a.first.second < b.first.second;
	}
	return a.first.first < b.first.first;
}

bool inside(int r, int c) {
	return r >= 0 && r < n && c >= 0 && c < n;
}


// 가장 가까이에 있어 태울 승객 찾기
pair<pair<int,int>, int> bfs(int r, int c, int energy, vector<vector<int>> &arr) {
	// r, c / 이동 횟수
	int min_cost = energy;
	vector<pair<pair<int,int>, int>> candidates;
	queue<pair<pair<int,int>, int>> q;
	vector<vector<bool>> visited(n, vector<bool>(n, false));
	q.push({{r, c}, 0});
	visited[r][c] = true;
	// 후보 고객 탐색
	while(!q.empty()) {
		int nr = q.front().first.first;
		int nc = q.front().first.second;
		int cost = q.front().second;

		q.pop();

		if(arr[nr][nc] < 0) {
			int idx = arr[nr][nc] * -1;
			if(cost <= min_cost) {
				min_cost = cost;
				candidates.push_back({{nr, nc}, cost});
			}
			else {
				break;
			}
		}

		for(int d = 0;d < 4;d++) {
			int nnr = nr + dr[d];
			int nnc = nc + dc[d];

			if(!inside(nnr, nnc)) continue;

			if(arr[nnr][nnc] == 1) continue;

			if(!visited[nnr][nnc] && cost < energy) {
				q.push({{nnr,nnc}, cost + 1});
				visited[nnr][nnc] = true;
			}
		}

	}

	if(candidates.size() == 0) {
		return {{-1, -1}, -1};
	}
	sort(candidates.begin(), candidates.end(), cmp);
	return candidates[0];
}

int move(int start_r, int start_c, int end_r, int end_c, vector<vector<int>> &arr) {
	vector<vector<bool>> visited(n, vector<bool>(n, false));
	queue<pair<pair<int,int>, int>> q;
	int answer = -1;
	q.push({{start_r, start_c}, 0});
	visited[start_r][start_c] = true;

	while(!q.empty()) {
		int r = q.front().first.first;
		int c = q.front().first.second;
		int cost = q.front().second;

		q.pop();

		if(r == end_r && c == end_c) {
			answer = cost;
			break;
		}

		for(int d = 0;d < 4;d++) {
			int nr = r + dr[d];
			int nc = c + dc[d];
			if(!inside(nr, nc) || arr[nr][nc] == 1) continue;

			if(!visited[nr][nc]) {
				visited[nr][nc] = true;
				q.push({{nr, nc}, cost + 1});
			}
		}
	}

	return answer;
}

int main() {
	int energy, r, c;
	cin >> n >> m >> energy;
	int answer = 0;
	vector<vector<int>> arr(n, vector<int>(n));
	vector<pair<int,int>> ends(m + 1);

	for(int i = 0;i < n;i++) {
		for(int j = 0;j < n;j++) {
			cin >> arr[i][j];
		}
	}

	cin >> r >> c;

	r -= 1;
	c -= 1;

	for(int i = 0;i < m;i++) {
		int start_r, start_c, end_r, end_c;
		cin >> start_r >> start_c >> end_r >> end_c;
		arr[start_r - 1][start_c - 1] = (i + 1) * -1;
		ends[i + 1] = {end_r - 1, end_c - 1};
	}

	while(energy >= 0 && m > 0) {
		pair<pair<int,int>, int>customer = bfs(r, c, energy, arr);

		int start_r = customer.first.first;
		int start_c = customer.first.second;
		int go_cost = customer.second;

		if(start_r == -1) {
			answer = -1;
			break;
		}

		int idx = arr[start_r][start_c] * -1;
		int end_r = ends[idx].first;
		int end_c = ends[idx].second;

		int move_cost = move(start_r, start_c, end_r, end_c, arr);

		// 성공하지 못한 고객이더라도 재탐색 방지 위해
		arr[start_r][start_c] = 0;
		if(move_cost < 0) {
			continue;
		}

		if(go_cost + move_cost > energy) {
			answer = -1;
			break;
		}
		else {
			energy -= go_cost - move_cost;
			r = end_r;
			c = end_c;
			m--;
		}

	}

	if(answer != -1) {
		answer = energy;
	}

	cout << answer << '\n';

}

참고한 질문 게시판

https://www.acmicpc.net/board/view/88714