[G2] 백준 19238번 스타트 택시 C++ 다익스트라, 해시맵, 우선순위 큐

리뷰

 

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

처음 봤을 땐 긴가민가 했는데 N값이 작아 충분히 해결할 수 있을 것 같아 다익스트라로 풀이하였다.

 

 

전역 변수

• n : 맵의 한 변의 길이를 저장할 변수
• m : 손님의 수를 저장할 변수
• f : 남은 연료의 양을 저장할 변수
• sx, sy : 택시의 현재 위치를 저장할 변수
• dx, dy : 4방향 탐색을 위한 방향 배열
• dist : 각 좌표에서 다른 좌표로 이동하기 위한 최단거리를 저장할 정수형 2차 벡터의 2차 배열
• Pos : 최단 거리를 구하기 위한 구조체, x, y좌표와, d 거리, index 손님 번호를 의미한다, 거리 순으로 오름차순, 같다면 x순으로 오름차순, 같다면 y순으로 오름차순 정렬한다.
• Pos2 : 손님과 목표의 위치를 저장하기 위한 구조체, x, y좌표만 저장한다.
• start : 손님의 위치를 저장하기 위한 해시맵 key는 손님 번호, value는 Pos2타입의 좌표를 저장한다.
• dest : 손님의 도착지 위치를 저장하기 위한 해시맵 key는 손님 번호, value는 Pos2타입의 좌표를 저장한다.

 

함수

1. dijkstra

void dijkstra(int x, int y, vector<vector<int>>& temp)

 

각 좌표에서 다른 좌표로 이동하기 위한 최단 거리를 구하는 함수

1. 매개변수로 시작 위치 좌표x, y와 현재 위치에서 갈 수 있는 최단 경로를 저장할 2차원 정수형 벡터 temp를 받는다.
2. Pos 타입의 우선순위 큐 pq를 초기화 하고, 시작 위치 x, y와 시작 거리 0을 push한다.
3. temp의 시작 위치 x, y는 0으로 초기화 한다.
4. pq가 빌 때 까지 while루프를 수행하며, 각 루프마다 요소를 한개씩 꺼내어 준다.
5. 요소의 위치로부터 4방향을 탐색하며 맵의 범위를 벗어나지 않고, 벽이 아니라면 이동을 진행해 준다.
6. temp의 최소값을 갱신해 나가며 시작 위치로부터 모든 위치로의 최단 거리를 구해준다.
7. temp를 참조형으로 전달하였기 때문에 따로 리턴할 필요는 없다.

 

문제풀이

1. n, m, f값을 입력 받고, n * n크기의 맵의 정보를 입력받아 준다.
2. 다시 n * n크기의 맵을 순회하며 각 좌표마다 최대 거리를 저장한 2차원 벡터 temp를 초기화 한다.
3. 만약 맵 상에서 값이 0이라면 dijkstra함수에 i, j와 temp를 매개변수로 전달하여 호출한다.
4. 갱신된 temp를 dist[i][j]의 값으로 저장해 준다.
5. 택시의 초기위치를 sx, sy에 입력 받아준다.
6. m개의 손님의 시작 위치와 목표 위치를 입력받는다.
7. start, dest에 손님 번호를 key로, 시작 위치와 목표 위치의 x, y좌표를 value로 저장해 준다.
8. dest가 빌 때 까지 while루프를 수행해 준다.
9. Pos타입의 우선순위 큐 pq를 초기화 한다.
10. start를 순회하며 모든 요소를 pq에 삽입해 준다. 이때의 인자는 x, y의 좌표와 dist[택시x][택시y][손님x][손님y]와 손님의 번호를 전달해 준다.
11. pq의 top에 해당하는 거리만큼 f를 빼준다, 이후 만약 f가 0보다 작다면 break처리해 준다.
12. 이제 택시 위치에서 목표 위치까지의 거리만큼 f를 빼준다, 이후 만약 f가 0보다 작다면 break처리해 준다.
13. break문에 걸리지 않았다면 택시 위치에서 목표 위치까지의 거리의 2배만큼 f에 더해준다.
14. 택시 위치를 목표위치로 갱신해 주고, start, dest에서 손님과 목표 위치를 제거해 준 뒤 pq에서 요소를 pop해준다.
15. 모든 탐색을 완료하고 dest가 비었다면 f값을 출력한다, 만약 비지 않았다면 -1을 출력해 준다.

---

요약하자면 다음과 같다.

1. 다익스트라를 통해 모든 좌표에서 다른 좌표까지의 이동 시 최단 거리를 dist로 저장한다.
2. dist를 기반으로 현재 택시 위치와 가장 가까운 손님 거리를 구해 우선순위 큐로 가장 가까운 손님을 찾는다.
3. 손님을 목표 위치까지 데려다 준 후 해당 택시의 위치에서 위 로직을 반복 수행한다.

 

트러블 슈팅

없음

 

 

참고 사항

• 거리의 값을 매우큰 값으로 설정하였으므로 손님을 태우거나 목표위치로 이동이 불가하다면 f는 0보다 작아진다.
• dest가 비지 않았다는 것은 모든 손님을 목표 지점까지 떨궈놓지 못했다는 말이다.

 

정답 코드

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

int n, m, f, sx, sy;
int lst[21][21];
int dx[] = { -1, 0, 0, 1 };
int dy[] = { 0, -1, 1, 0 };
vector<vector<int>> dist[21][21];

struct Pos {
	int x, y, d, index;
	bool operator<(const Pos& other) const {
		if (d == other.d) {
			if (x == other.x) return y > other.y;
			return x > other.x;
		}
		return d > other.d;
	}
};

struct Pos2 {
	int x, y;
};

unordered_map<int, Pos2> start;
unordered_map<int, Pos2> dest;

void dijkstra(int x, int y, vector<vector<int>>& temp) {
	priority_queue<Pos> pq;
	pq.push({ x, y, 0 });
	temp[x][y] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.x, cy = pos.y, cd = pos.d;
		if (temp[cx][cy] < cd) continue;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i], nd = cd + 1;
			if (0 < nx && nx <= n && 0 < ny && ny <= n && !lst[nx][ny]) {
				if (temp[nx][ny] > nd) {
					temp[nx][ny] = nd;
					pq.push({ nx, ny, nd });
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m >> f;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			cin >> lst[i][j];

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			vector<vector<int>> temp(n + 1, vector<int>(n + 1, 2e9));
			if (!lst[i][j]) dijkstra(i, j, temp);
			dist[i][j] = temp;
		}
	}

	cin >> sx >> sy;
	for (int i = 1; i <= m; ++i) {
		int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
		start[i] = { x1, y1 };
		dest[i] = { x2, y2 };
	}

	while (!dest.empty()) {
		priority_queue<Pos> pq;
		for (auto i : start) {
			pq.push({ i.second.x, i.second.y, dist[sx][sy][i.second.x][i.second.y], i.first });
		}
		Pos pos = pq.top();
		f -= pos.d;
		if (f < 0) break;
		Pos2 pos2 = dest[pos.index];
		f -= dist[pos.x][pos.y][pos2.x][pos2.y];
		if (f < 0) break;
		f += dist[pos.x][pos.y][pos2.x][pos2.y] * 2;
		sx = pos2.x, sy = pos2.y;
		start.erase(pos.index);
		dest.erase(pos.index);
		pq.pop();
	}

	if (dest.empty()) cout << f;
	else cout << -1;
}