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

www.acmicpc.net/problem/19238

19238번: 스타트 택시

너비 우선 탐색 (bfs)를 통해 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int n, m, energe;
int board[21][21];
pair<int, int> taxi;
pair<int, int> dest[401]; //각 고객의 목적지 저장
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

pair<int, int> Go_dest(pair<int, int> client_start, pair<int, int> client_dest)
{
	vector<vector<int>> discovered(21, vector<int>(21, 0));
	vector<vector<int>> depth(21, vector<int>(21, 0));
	queue<pair<int, int>> q;

	discovered[client_start.first][client_start.second] = 1;
	depth[client_start.first][client_start.second] = 0;
	q.push(client_start);

	while (!q.empty())
	{
		pair<int, int> here = q.front();
		q.pop();

		//연료보다 많이 가야될때
		if (energe < depth[here.first][here.second])
			return make_pair(-1, -1);

		//고객 목적지에 도착 했을때
		if (here == client_dest)
		{
			energe -= depth[here.first][here.second];
			energe += depth[here.first][here.second] * 2;
			return here;
		}

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);

			if (there.first >= 1 && there.first <= n && there.second >= 1 && there.second <= n && board[there.first][there.second] != -1 && discovered[there.first][there.second] == 0)
			{
				discovered[there.first][there.second] = 1;
				depth[there.first][there.second] = depth[here.first][here.second] + 1;
				q.push(there);
			}
		}
	}

	return make_pair(-1, -1);
}

//가까운 고객을 찾는다
pair<int, int> Find_client(pair<int, int> start)
{
	vector<vector<int>> discovered(21, vector<int>(21, 0));
	vector<vector<int>> depth(21, vector<int>(21, 0));
	queue<pair<int, int>> q;

	vector<pair<int, int>> temp_dest; //가까운 고객 후보
	int temp_dest_depth = 987654321;

	discovered[start.first][start.second] = 1;
	depth[start.first][start.second] = 0;
	q.push(start);

	while (!q.empty())
	{
		pair<int, int> here = q.front();
		q.pop();

		//고객후보들을 전부 찾았을때
		if (temp_dest_depth < depth[here.first][here.second])
			break;

		//연료보다 많이 가야될때
		if (energe < depth[here.first][here.second])
			break;

		//고객을 찾았을때
		if (board[here.first][here.second] != 0)
		{
			temp_dest.push_back(here);
			temp_dest_depth = depth[here.first][here.second];
			continue;
		}

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);

			if (there.first >= 1 && there.first <= n && there.second >= 1 && there.second <= n && board[there.first][there.second] != -1 && discovered[there.first][there.second] == 0)
			{
				discovered[there.first][there.second] = 1;
				depth[there.first][there.second] = depth[here.first][here.second] + 1;
				q.push(there);
			}
		}
	}

	//갈 수 있는 고객이 없을때
	if (temp_dest.size() == 0)
		return make_pair(-1, -1);

	sort(temp_dest.begin(), temp_dest.end());
	energe -= temp_dest_depth;

	return temp_dest[0];
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m >> energe;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			int input;
			cin >> input;

			if (input == 1)
				input = -1; //벽은 -1로 표시한다

			board[i][j] = input;
		}
	}

	cin >> taxi.first >> taxi.second;

	for (int i = 1; i <= m; i++)
	{
		int start_row;
		int start_col;
		int dest_row;
		int dest_col;

		cin >> start_row >> start_col >> dest_row >> dest_col;

		board[start_row][start_col] = i; //손님 위치 표시
		dest[i] = make_pair(dest_row, dest_col); //손님 목적지 저장
	}

	bool fail = false;
	pair<int, int> here = taxi; //taxi위치에서 시작
	for (int i = 1; i <= m; i++)
	{
		pair<int, int> client = Find_client(here); //here위치에서 고객을 찾는다

		//갈 수 있는 고객이 없을때
		if (client.first == -1 && client.second == -1)
		{
			fail = true;
			break;
		}

		//가까운 고객의 번호
		int client_number = board[client.first][client.second];
		board[client.first][client.second] = 0; //board에 처리

		//고객을 목적지까지 태워다 준 위치
		here = Go_dest(client, dest[client_number]);

		//고객을 목적지까지 데려다 줄 수 없을때
		if (here.first == -1 && here.second == -1)
		{
			fail = true;
			break;
		}

	}

	if (fail == true)
		cout << -1;

	else
		cout << energe;

	return 0;
}