[백준/BOJ] 백준 4991번 : 로봇 청소기

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

4991번: 로봇 청소기

시작 위치와 더러운 칸을 정점으로 해서, 각각의 정점에서 다른 정점으로 가는 최단 경로를 구한 뒤 시작 위치를 시작해 모든 정점을 들릴 수 있는 경로중  가장 작은 이동거리를 구한다

 

코드

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

int w, h;
int board[20][20];
int discovered[20][20];
int depth[20][20];
int dx_dy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
int trash_number;
vector<pair<pair<int, int>, int>> start_and_trash;
int dist[11][11];

int Solve(vector<int>& order, vector<int>& selected)
{
	int ret = 987654321;

	//경로를 구했을때
	if (order.size() == start_and_trash.size())
	{
		ret = 0;

		//경로의 이동횟수를 구한다
		for (int i = 1; i < order.size(); i++)
		{
			ret += dist[order[i - 1]][order[i]];
		}

		return ret;
	}

	for (int i = 1; i < start_and_trash.size(); i++)
	{
		//i정점이 경로에 포함되지 않았을때
		if (selected[i] == 0)
		{
			order.push_back(i);
			selected[i] = 1;

			ret = min(ret, Solve(order, selected));

			order.pop_back();
			selected[i] = 0;
		}
	}

	return ret;
}

//start정점에서 다른 각각의 정점으로 가는 최단 경로(이동횟수의 최소)를 구한다
//반환값은 각각의 정점으로 모두 최단거리를 구했는지(도달할 수 있는지)를 반환한다
bool pathFind(pair<int, int> start, int start_number)
{
	memset(discovered, 0, sizeof(discovered));
	memset(depth, 0, sizeof(depth));
	vector<int> check(start_and_trash.size(), 0); //최단 경로가 구해진 정점을 체크하기 위해서

	discovered[start.first][start.second] = 1;
	depth[start.first][start.second] = 0;
	check[start_number] = 1;

	queue<pair<int, int>> q;
	q.push(start);

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

		//최단 경로를 구하지 못한 정점을 발견했을때
		if (board[here.first][here.second] >= 0 && check[board[here.first][here.second]] == 0)
		{
			dist[start_number][board[here.first][here.second]] = depth[here.first][here.second];
			check[board[here.first][here.second]] = 1;
		}

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

			if (there.first >= 0 && there.first < h && there.second >= 0 && there.second < w  && discovered[there.first][there.second] == 0 && board[there.first][there.second] != -2)
			{
				discovered[there.first][there.second] = 1;
				depth[there.first][there.second] = depth[here.first][here.second] + 1;

				q.push(there);
			}
		}

	}

	//각각의 정점으로 가는 최단 경로가 모두 만들어 졌는지 확인
	bool reach = true;
	for (int i = 0; i < check.size(); i++)
	{
		//최단 경로가 만들어지지 않은 정점일때(갈 수 없는 정점이 있을때)
		if (check[i] == 0)
		{
			reach = false;
			break;
		}
	}

	return reach;
}

void Pre()
{
	trash_number = 1;
	memset(board, -1, sizeof(board)); //빈칸은 -1
	memset(dist, 987654321, sizeof(dist));
	start_and_trash.clear();
}

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

	string temp;

	while (1)
	{
		Pre();

		cin >> w >> h;

		if (w == 0 && h == 0)
			break;

		for (int i = 0; i < h; i++)
		{
			cin >> temp;
			for (int j = 0; j < w; j++)
			{
				if (temp[j] == '*')
				{
					//더러운칸은 각각 번호(1이상)로 매긴뒤, board의 해당칸에 그 번호를 넣는다
					board[i][j] = trash_number;

					//시작위치와 더러운칸의 정보들은 저장해 놓는다(정점 정보 저장)
					start_and_trash.push_back(make_pair(make_pair(i, j), trash_number));

					trash_number++;
				}

				else if (temp[j] == 'x')
					board[i][j] = -2; //가구가 있는칸은 board에 -2로 채운다

				else if (temp[j] == 'o')
				{
					board[i][j] = 0; //시작위치는 0으로 채운다

					//시작위치와 더러운칸의 정보들은 저장해 놓는다(정점 정보 저장)
					start_and_trash.push_back(make_pair(make_pair(i, j), 0));
				}
			}
		}

		bool reach = true;

		//시작위치와 더러운칸 위치들 각각에서 다른 지점들로 가는 최단 경로를 찾는다
		for (int i = 0; i < start_and_trash.size(); i++)
		{
			//시작위치와 더러운칸들 중 도달할 수 없는곳이 있을때
			if (!pathFind(start_and_trash[i].first, start_and_trash[i].second))
			{
				reach = false;
				cout << -1 << "\n";
				break;
			}
		}

		if (reach)
		{
			vector<int> order;
			vector<int> selected(start_and_trash.size(), 0);

			//시작 위치 정점에서 시작해서 더러운칸 정점 들을 모두 방문하는 경로중 이동횟수의 최솟값을 구한다		
			//순서는 시작위치(0번정점)부터 시작한다
			order.push_back(0);
			selected[0] = 1;
			cout << Solve(order, selected) << "\n";
		}
	}

	return 0;
}