BOJ_4991 : 로봇 청소기

문제

오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.

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

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

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

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

입력

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

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

• .: 깨끗한 칸
• *: 더러운 칸
• x: 가구
• o: 로봇 청소기의 시작 위치 더러운 칸의 개수는 10개를 넘지 않으며, 로봇 청소기의 개수는 항상 하나이다.

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

출력

각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.

C++ 코드

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

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

vector< vector<int> > bfs(vector< string >& s, int a, int b) {
	int h = s.size();
	int w = s[0].size();
	
	queue< pair<int, int> > q;
	vector< vector<int> > dist(h, vector<int>(w, -1));
	q.push(make_pair(a, b));
	dist[a][b] = 0;

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];
			if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
			if (dist[nx][ny] != -1  ) continue;
			if (s[nx][ny] != 'x') {
				dist[nx][ny] = dist[x][y] + 1;
				q.push(make_pair(nx, ny));
			}
		}
	}

	return dist;
}

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

	while (1) {
		int w, h;
		cin >> w >> h;
		if (w == 0 && h == 0) break;
		// 00 이면 종료

		vector< string > s(h);
		vector< pair<int, int> > b(1);
		//청소기와 먼지 위치
		for (int i = 0; i < h; i++) {
			cin >> s[i];
		}

		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (s[i][j] == 'o') {
					b[0] = make_pair(i, j);
				}
				else if(s[i][j] == '*') {
					b.push_back(make_pair(i, j));
				}				
			}
		}
		int dust_size = b.size();
		vector< vector<int> > d(dust_size, vector<int>(dust_size));
		vector< vector<int> > dist;
		bool ok = true;
		for (int i = 0; i < dust_size; i++) {
			int x = b[i].first;
			int y = b[i].second;
			dist = bfs(s, x, y);
			for (int j = 0; j < dust_size; j++) {
				d[i][j] = dist[b[j].first][b[j].second];
				if (d[i][j] == -1)
					ok = false;
			}
		}

		// 청소 못하는 경우
		if (!ok) {
			cout << -1 << '\n';
			continue;
		}

		// 비트마스크
		vector<int> mask(dust_size);
		for (int i = 0; i < dust_size; i++) {
			mask[i] = i;
		}
		int ans = h * w;
		do {
			int cnt = 0;
			if (mask[0] != 0) break;
			//시작점은 무조건 청소기 위치

			for (int i = 0; i + 1 < dust_size; i++) {
				cnt += d[mask[i]][mask[i + 1]];
			}
			if (ans > cnt) ans = cnt;
		} while (next_permutation(mask.begin(), mask.end()));

		cout << ans << '\n';
	}
	return 0;
}