BOJ 19238 스타트 택시

DFS/BFS 알고리즘과 시뮬레이션이 합쳐진 구현 문제이다. 세부조건이 까다로워서 처음부터 간결한 코드를 작성하는 것이 요구된다고 생각한다.

그래서 구조체 대신에 클래스를 이용하여 복잡한 변수를 초기화하고, 클래스의 연산자 오버로딩으로 정렬 우선순위를 재정의할 수 있었다.

 

"알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다." → BFS 알고리즘 이용

"백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다."

→ 우선순위를 정하면

1. 아직 도착지로 가지 못한 승객

2. 택시와의 최단거리가 가장 짧은 승객

3. 행 번호가 작은 승객

4. 열 번호가 작은 승객

 

우선순위가 4개나 되므로, std::tie 와 std::sort 를 이용하여 간단하고 빠르게 우선순위 승객을 찾는다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <tuple>
#include <string>
#include <algorithm>

using namespace std;

void initBOJ() {
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(false);
}

class Node {
public:
	int x, y, dist;
	Node(int x, int y, int dist) {
		this->x = x;
		this->y = y;
		this->dist = dist;
	}
};

class Guest {
public:
	int dist, x1, y1, x2, y2;
	bool traveled = false;

	Guest(int dist, int x1, int y1, int x2, int y2) {
		this->dist = dist;
		this->x1 = x1;
		this->y1 = y1;
		this->x2 = x2;
		this->y2 = y2;
	}

	bool operator < (Guest& G) {
		return tie(this->traveled, this->dist, this->x1, this->y1) < tie(G.traveled, G.dist, G.x1, G.y1);
	}

	friend ostream& operator<< (ostream& os, const Guest& G) {
		char buff[100];
		snprintf(buff, sizeof(buff), "(traveled: %d, dist: %d, x1: %d, y1: %d)", G.traveled, G.dist, G.x1, G.y1);
		string str_buff = buff;
		os << str_buff;
		return os;
	}
};

// Check all guests have traveled to their destination
bool AllTraveled(vector<Guest>& guests) {
	for (auto& guest : guests) {
		if (!guest.traveled) {
			return false;
		}
	}

	return true;
}

// Returns a minimum distance of the path from (x1, y1) to (x2, y2) on board
// If there is no such path, then returns -1
int bfs_distance(vector<vector<int>>& board, int x1, int y1, int x2, int y2) {
	int N = board.size();
	int ret_dist = -1;
	vector<vector<bool>> visited(N, vector<bool>(N, false));

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

	queue<Node> q;
	q.push(Node(x1, y1, 0));
	visited[x1][y1] = true;

	while (!q.empty()) {
		Node cur = q.front();
		q.pop();

		if (cur.x == x2 && cur.y == y2) {
			ret_dist = cur.dist;
			break;
		}

		for (int i = 0; i < 4; i++) {
			int nx = cur.x + dx[i];
			int ny = cur.y + dy[i];

			if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
			if (visited[nx][ny]) continue;
			if (board[nx][ny] == 1) continue;

			q.push(Node(nx, ny, cur.dist + 1));
			visited[nx][ny] = true;
		}
	}

	return ret_dist;
}

// Print some member variables of Guest vector
void print_guests(vector<Guest>& guests) {
	cout << "\n====================\n";
	for (auto& guest : guests) {
		cout << guest << '\n';
	}
	cout << "====================\n";
}

int main() {
	//freopen("input.txt", "r", stdin);
	initBOJ();

	int N, M, fuel;
	cin >> N >> M >> fuel;
	vector<vector<int>> board(N, vector<int>(N, 0));

	// input map information
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
		}
	}

	// input (x, y) of a taxi and adjust (x, y)
	int x_taxi, y_taxi;
	cin >> x_taxi >> y_taxi;
	x_taxi -= 1;
	y_taxi -= 1;

	// input (x, y) of guests
	int x1, y1, x2, y2;
	vector<Guest> guests;
	for (int i = 0; i < M; i++) {
		cin >> x1 >> y1 >> x2 >> y2;
		guests.push_back(Guest(0, x1 - 1, y1 - 1, x2 - 1, y2 - 1));
	}

	// simulation
	int dist;
	while (!AllTraveled(guests) && fuel > 0) {
		for (auto& guest : guests) {
			if (guest.traveled) continue;

			dist = bfs_distance(board, x_taxi, y_taxi, guest.x1, guest.y1);
			if (dist == -1) {
				dist = fuel + 1; // cannot reach
			}
			guest.dist = dist;
		}

		sort(guests.begin(), guests.end());

		//print_guests(guests);

		fuel -= guests[0].dist;
		if (fuel < 0) {
			fuel = -1;
			break;
		}

		dist = bfs_distance(board, guests[0].x1, guests[0].y1, guests[0].x2, guests[0].y2);
		if (dist == -1) {
			dist = fuel + 1;
		}
		x_taxi = guests[0].x2;
		y_taxi = guests[0].y2;
		fuel -= dist;
		
		if (fuel < 0) {
			fuel = -1;
			break;
		}

		fuel += (2 * dist);
		guests[0].traveled = true;
	}

	//print_guests(guests);
	cout << fuel;
	return 0;
}