[BOJ-4991] 로봇 청소기 (C++)

백준 4991 로봇 청소기

 

4991번: 로봇 청소기

 

 

문제 설명

 

 - 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려 한다.

 

 - 방은 크기가 1x1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1x1이다.

 

 - 각 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있다.

 

 - 로봇 청소기는 더러운 칸을 방문해 깨끗한 칸으로 바꿀 수 있다.

 

 - 일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1x1 이다.

 

 - 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다.

 

 - 로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다.

   또한, 로봇은 같은 칸을 여러 번 방문할 수 있다.

 

 - 방의 정보가 주어졌을 때, 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는

   이동 횟수의 최솟값을 한 줄에 출력한다.

 

 - 만약 방만할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.

---

 

입력 값

 

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

 

 - 각 테이스트 케이스의 첫째 줄에는 방의 가로 크기 w와 세로 크기 h가 주어진다.

   ( 1 <= w, h <= 20 )

 

 - 둘째 줄부터 h개의 줄에는 방의 정보가 주어진다.

 

 - 방의 정보는 4가지 문자로만 이루어져 있다.

   . : 깨끗한 칸

   * : 더러운 칸

   x : 가구

    o : 로봇 청소기의 시작 위치

 

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

 

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

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제는 더러운 칸을 깨끗한 칸으로 만드는 모든 경우의 수를 구하고, 그 중 최소값을 구하는 문제이다.

 

 - 더러운 칸을 방문하는 순서도 모두 고려해야 한다.

 

 - 간단하게 생각하자면, 더러운 칸을 방문하는 모든 경우의 수를 구하고, 해당 경우의 수를

   바탕으로 더러운 칸을 방문하여 구할 수 있다.

 

 - 이 경우에는 모든 칸을 방문하는 경우의 수 10! = 360만과

   이 순서대로 최단 경로를 찾는 경우의 수는 각 점에서 다른 위치를 bfs를 이용하여 구할 수 있기 때문에 20x20 = 400이고,  

   더러운 칸은 모두 10칸이기 떄문에 400x10 = 4000이 된다.

 

 - 즉, 360만 x 4000 이기 때문에 시간 안에는 불가하다.

 

 - 간단하게 생각하는 과정을 잘 살펴보면, 반복되는 과정이 있음을 알 수 있다.

 

 - 하나의 더러운 칸에서 다른 더러운 칸으로 최단 가는 경로는 항상 같다.

   즉, 더러운 칸끼리 이동하는 최단 경로와 그 값은 항상 같다는 것이다.

 

 - 메모이제이션을 이용하여, 모든 더러운 칸끼리 최단 경로를 저장하면, 중복 호출을 막을 수 있다.

 

 - 이 방법을 이용하면, 더러운 칸 끼리의 경로를 미리 구했기 때문에

   모든 경로에서 매번 계산할 필요가 없어진다.

 

 - 즉, 시간 복잡도는 360만 + 4000이 된다. 

 

 - 이 문제를 푸는 과정은 다음과 같다.

   1. 더러운 칸 사이의 최단 경로를 미리 구한다.

   2. 더러운 칸을 방문하는 모든 순서를 구한다.

   3. 시작점에서 더러운 칸을 방문하는 순서에 따라 값을 구하고, 그 중 최솟값을 구한다. 

 

 

---

 

 

소스 코드

 

#include <bits/stdc++.h>
#include<unordered_map>
using namespace std;

#define DIRTY 1
#define CLEAN 0
#define OBSTACLE -1

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


int boards[21][21];

int trashToTrashLength[21][21];
int visited[21][21];
int startToTrash[21];

int w, h;
char c;


// 해당 지점 쓰레기 위치에서 다른 위치 까지 거리 구하기
void bfs(int y, int x) {
	queue<pair<int, int>> q;
	q.push({ y,x });
	fill(&visited[0][0], &visited[0][0] + 21 * 21, INT_MAX);
	visited[y][x] = 0;

	while (!q.empty()) {

		int sy = q.front().first;
		int sx = q.front().second;
		int nCost = visited[sy][sx]+1;
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ny = sy + dy[d];
			int nx = sx + dx[d];

			if (ny < 0 || nx < 0 || ny >= h || nx >= w || visited[ny][nx] <= nCost || boards[ny][nx]==OBSTACLE) {
				continue;
			}

			visited[ny][nx] = nCost;
			q.push({ ny,nx });

		}

	}


}

// 시작점에서 쓰레기 줍는 최단 거리 구하기
int findMinPath(int y, int x, vector<pair<int, int>> &dirtyPoint) {
	vector<int> trashOrder;
	int result = INT_MAX;

	// 시작점에서 쓰레기 까지 위치 구하기
	bfs(y, x);

	for (int j = 0; j < dirtyPoint.size(); j++) {
		startToTrash[j] = visited[dirtyPoint[j].first][dirtyPoint[j].second];
	}

	// 각 쓰레기에서 다른 쓰레기 까지 위치 구하기
	for (int i = 0; i < dirtyPoint.size(); i++) {
		bfs(dirtyPoint[i].first, dirtyPoint[i].second);

		for (int j = 0; j < dirtyPoint.size(); j++) {
			if (i == j) {
				continue;
			}
			trashToTrashLength[i][j] = visited[dirtyPoint[j].first][dirtyPoint[j].second];
		}
		trashOrder.push_back(i);
	}

	// 쓰레기 줍는 모든 순서 살펴보기
	do {
		int lengthSum = startToTrash[trashOrder[0]];
		
		for (int i = 0; i < trashOrder.size()-1; i++) {
			if (trashToTrashLength[trashOrder[i]][trashOrder[i+1]]==INT_MAX) {
				lengthSum = -1;
				break;
			}
			lengthSum += trashToTrashLength[trashOrder[i]][trashOrder[i+1]];
		}
		if (lengthSum == -1) {
			continue;
		}
		result = min(result, lengthSum);

	} while (next_permutation(trashOrder.begin(), trashOrder.end()));

	// 갈 수 없는 경로가 있는 경우
	if (result == INT_MAX) {
		result = -1;
	}

	return result;

}

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


	int startY, startX;

	cin >> w >> h;

	while (w != 0 && h != 0) {

		fill(&boards[0][0], &boards[0][0] + 21 * 21, 0);
		fill(&trashToTrashLength[0][0], &trashToTrashLength[0][0] + 21 * 21, 0);

		vector<pair<int, int>> dirtyPoint;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> c;
				if (c == '*') {
					boards[i][j] = DIRTY;
					dirtyPoint.push_back({ i,j });
				}
				else if (c == 'x'){
					boards[i][j] = OBSTACLE;
				}
				else if (c == 'o') {
					startY = i;
					startX = j;
					
				}
			}
		}
		cout << findMinPath(startY, startX, dirtyPoint) << endl;

		cin >> w >> h;


	}


	return 0;
}