[C/C++] 백준 - 4991번 : 로봇 청소기

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을 출력한다.

 

요즘 학교를 복학해서 수업과 알고리즘 공부를 병행하려니 정말 시간이 부족하다.

그래서 저번 일주일 간은 문제를 많이 못풀고 쉬운 문제만 많이 풀었는데 문제의 감이 조금 떨어진 것 같다.

 

이 문제는 FloodFill과 순열을 이용해서 해결할 수 있다.

나도 처음에 어떻게 접근해야할지 한 시간 정도 고민하다가 떠오르지 않아서 깔끔히 포기하고 유튜브에서 강의를 찾아봤다. FloodFill로 더러운 공간과 로봇 청소기의 위치를 덱에 넣어주었다. 덱에 넣은 이유는 첫번째 인덱스에 로봇청소기 위치를 고정하기 위해서이다. 그리고 각 칸에서부터 다른칸까지의 거리를 테이블에 넣어주었고, 순열을 이용해서 모든 경우의 수를 확인해주는 방법으로 풀었다. 

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <map> 
#include <algorithm>
#include <cmath>
#define ll long long
#define INF 987654321
#define CUNLINK ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define MAX 100000 + 1
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int n, m, Cnt, answer = INF;
int board[22][22];
int visited[22][22];
int dist[22][22];
int op[11], check[11];
bool isEnd = false;
deque<pil> dq;
queue<pil> Temp;

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

bool isValid(int y, int x) {
	return (0 <= y && y < m && 0 <= x && x < n);
}

void Input() {
	for (int i = 0; i < m; i++) {
		string s; cin >> s;
		for (int j = 0; j < n; j++) {
			if (s[j] == '.') board[i][j] = 0;
			else if (s[j] == 'x') board[i][j] = -1;
			else if (s[j] == 'o') {
				dq.push_front({ i,j });
				board[i][j] = 1;
			}
			else if(s[j]=='*'){
				Cnt++;
				dq.push_back({ i, j });
				board[i][j] = 1;
			}
		}
	}
}

int BFS(int cy, int cx, int Py, int Px) {
	queue<pil> q;
	q.push({ cy, cx });
	visited[cy][cx] = 1;

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

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (isValid(ny, nx) && !visited[ny][nx]) {
				if (ny == Py && nx == Px) return visited[y][x];
				if (board[ny][nx] != -1) {
					visited[ny][nx] = visited[y][x] + 1;
					q.push({ ny, nx });
				}
			}
		}
	}
	return -1;
}

void Cal_Dist(){
	for (int i = 0; i < dq.size(); i++) {
		int curY = dq[i].first;
		int curX = dq[i].second;

		for (int j = 0; j < dq.size(); j++) {
			if (i == j) dist[i][j] = 0;
			else {
				memset(visited, 0, sizeof(visited));
				int d = BFS(curY, curX, dq[j].first, dq[j].second);
				if (d == -1) {
					isEnd = true;
					break;
				}
				dist[i][j] = d;
				dist[j][i] = d;
			}
		}
		if (isEnd) break;
	}
}

void func(int depth) {
	if (depth == Cnt) {
		int Total = 0;
		Total += dist[0][op[0]];
		for (int i = 1; i < Cnt; i++) {
			Total += dist[op[i - 1]][op[i]];
		}
		answer = min(Total, answer);
		return;
	}

	for (int i = 1; i < dq.size(); i++) {
		if (!check[i]) {
			op[depth] = i;
			check[i] = true;

			func(depth + 1);

			check[i] = false;
		}
	}
}

int main() {
	CUNLINK;
	while (1) {
		isEnd = false, Cnt = 0, answer = INF;
		memset(op, 0, sizeof(op)); 
		memset(dist, 0, sizeof(dist));
		cin >> n >> m;
		if (!n && !m) break;
		Input();
		Cal_Dist();
		if (isEnd) {
			cout << -1 << endl;
		}
		else {
			func(0);
			if (answer == INF) answer = -1;
			cout << answer << endl;
		}
		dq.clear();
	}

	return 0;
}