[BOJ/백준 4991/C++] 로봇 청소기

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

4991번: 로봇 청소기

 

[문제 요약]

- 방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다.

 

- 일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다. 

- 로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다.

- 방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

 

[문제 조건]

- 입력은 여러 개의 테스트케이스로 이루어져 있다.

- 각 테스트 케이스의 첫째 줄에는 방의 가로 크기 w와 세로 크기 h가 주어진다. (1 ≤ w, h ≤ 20) 둘째 줄부터 h개의 줄에는방의 정보가 주어진다. 방의 정보는 4가지 문자로만 이루어져 있으며, 각 문자의 의미는 다음과 같다.

• .: 깨끗한 칸
• *: 더러운 칸
• x: 가구
• o: 로봇 청소기의 시작 위치

- 더러운 칸의 개수는 10개를 넘지 않으며, 로봇 청소기의 개수는 항상 하나이다.

- 입력의 마지막 줄에는 0이 두 개 주어진다.

- 시간 제한 : 1초

- 메모리 제한 : 256MB

 

[문제 풀이]

이번 문제는 생각보다 어렵다고 느꼈는데 막상 풀고나면 쉬웠던 문제였다.

 

필자는 처음에 데이터를 입력받으면서 로봇의 위치와 치워야될 위치에 대한 위치 정보를 미리 저장해놓고, 각 위치별로 다른 위치까지의 최단 거리를 2차원 배열의 형태로 저장해두었다.

 

최단 거리를 구할때는 BFS를 이용하여 구하였다.

 

그 다음 현재 로봇위치에서 가장 가까운 더러운 칸으로 움직이는 방식으로 정답을 구하려고 했지만 이 방법은 잘못된 방법이였다.

 

그리디하게 가장 가까운 위치먼저 이동을 하게 되면 이동횟수가 더 적은 경로에 대해서 무시가 되는 경우가 발생하게 된다.

 

따라서 더러운 칸의 위치들의 순열을 구해서 모든 경우에 대해서 거리를 구한 다음 최솟값을 출력하는 브루트 포스 문제였다.

 

문제 조건에서 더러운 칸은 10개를 넘지 않아서 최대 10개의 경우 10! = 3628800의 경우의 수가 나오지만 테스트 케이스가 몇개인지 명시되어있지 않아 처음에 배제하고 고민했었는데 브루트포스가 올바른 방법이여서 허무했던 문제였다.

 

[소스 코드]

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

#define INF 987654321
#define mod 1000000
#define pii pair<int,int>

using namespace std;

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

struct cmp
{
	bool operator()(pair<pii, int>& a, pair<pii, int>& b)
	{
		return a.second > b.second;
	}
};

int dist_of_two(int R, int C, vector<vector<char>> &mp, pii a, pii b)
{
	vector<vector<bool>> ck(R, vector<bool>(C, 0));

	priority_queue<pair<pii,int>, vector<pair<pii,int>> , cmp> pq;
	pq.push({ a, 0 });
	ck[a.first][a.second] = true;

	while (!pq.empty())
	{
		pair<pii, int> tmp = pq.top(); pq.pop();

		if (tmp.first == b) return tmp.second;

		for (int i = 0; i < 4; i++)
		{
			int nx = tmp.first.second + dx[i];
			int ny = tmp.first.first + dy[i];

			if (nx < 0 || ny < 0 || nx >= C || ny >= R) continue;
			if (ck[ny][nx]) continue;
			if (mp[ny][nx] == 'x') continue;

			ck[ny][nx] = true;
			pq.push({ {ny,nx}, tmp.second + 1 });
		}
	}

	return 0;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	while (1)
	{
		int R, C;
		cin >> C >> R;

		if (R == 0 && C == 0) break;

		vector<vector<char>> mp(R, vector<char>(C, 0));
		vector<pii> dirt;
		vector<pii> tmp2;
		pii robot;

		for (int i = 0; i < R; i++)
		{
			for (int j = 0; j < C; j++)
			{
				cin >> mp[i][j];
				if (mp[i][j] == 'o') { robot = { i,j }; }
				else if (mp[i][j] == '*') tmp2.push_back({ i,j });
			}
		}
		dirt.push_back(robot);
		for(int i=0;i<tmp2.size(); i++) dirt.push_back(tmp2[i]);
		vector<vector<int>> distance(dirt.size(), vector<int>(dirt.size(), 0));
		for (int i = 0; i < dirt.size(); i++)
		{
			for (int j = i + 1; j < dirt.size(); j++)
			{
				distance[i][j] = dist_of_two(R, C, mp, dirt[i], dirt[j]);
				distance[j][i] = distance[i][j];
			}
		}

		//도달 할 수 없는 더러운 칸이 존재하는지 확인
		bool cant_place = false;
		for (int i = 0; i < dirt.size(); i++)
		{
			for (int j = 0; j < dirt.size(); j++)
			{
				if (i == j) continue;

				if (distance[i][j] == 0) { cant_place = true; break; }
			}
			if (cant_place) break;
		}
		if (cant_place)
		{
			cout << "-1\n";
			continue;
		}

		vector<int> tmp;
		for (int i = 1; i < dirt.size(); i++) tmp.push_back(i);
		
        //순열을 구해서 모든 경우를 확인함
		int ans = INF;
		do
		{
			int cur_node = 0;
			int sum = 0;
			for (int i = 0; i < tmp.size(); i++)
			{
				sum += distance[cur_node][tmp[i]];
				cur_node = tmp[i];
			}
			ans = min(ans, sum);
		} while (next_permutation(tmp.begin(), tmp.end()));
		
		if (ans == 0) cout << "-1\n";
		else cout << ans << "\n";
	}
}

 

굳