로봇 청소기 (feat. 백준, 4991번)

로봇 청소기
https://www.acmicpc.net/problem/4991

4991번: 로봇 청소기

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
int W, H, SX, SY, ans, dx[4], dy[4], dist[21][21];
char arr[21][21];
bool visit[21][21];
pair<int, int> dusts[11];
int dust_permutate[10];
bool check_dust[10];
int dp[11][11];		// (x1,y1)->(x2,y2) 이동 거리. [0]은 청소기 시작지점. [1]부터 먼지
bool bfs(register int sx, register int sy, register int ex, register int ey) {
	memset(visit, false, sizeof(visit));
	queue<pair<int, int>> q;
	q.push(make_pair(sx, sy));
	visit[sx][sy] = true;
	dist[sx][sy] = 0;
	while (!q.empty()) {
		auto p = q.front(); q.pop();
		register int x = p.first, y = p.second;
		for (register int d = 0, nx, ny; d < 4; ++d) {
			nx = x + dx[d], ny = y + dy[d];
			if (1 <= nx && nx <= H && 1 <= ny && ny <= W && arr[nx][ny] != 'x' && !visit[nx][ny]) {
				visit[nx][ny] = true, dist[nx][ny] = dist[x][y] + 1;
				if (nx == ex && ny == ey)
					return true;
				q.push(make_pair(nx, ny));
			}
		}
	}
	return false;
}
void dfs(register int dust_count, const register int& total_dust_count) {
	if (dust_count == total_dust_count) {		// 먼지 위치 인덱스에 대한 순열
		memset(dist, 0, sizeof(dist));
		register int sx = SX, sy = SY, s = 0, distance = 0;
		for (register int i = 0; i < total_dust_count; ++i) {
			if (dp[s][dust_permutate[i]] == 0) {
				if (bfs(sx, sy, dusts[dust_permutate[i]].first, dusts[dust_permutate[i]].second)) {
					sx = dusts[dust_permutate[i]].first, sy = dusts[dust_permutate[i]].second;	// 다음 시작점 갱신
					dp[s][dust_permutate[i]] = dp[dust_permutate[i]][s] = dist[sx][sy];	// s->먼지 인덱스, 먼지 인덱스->s 로의 dp 갱신
					distance += dist[sx][sy];
				}
				else {
					ans = -1;
					return;
				}
			}
			else {
				sx = dusts[dust_permutate[i]].first, sy = dusts[dust_permutate[i]].second;	// 다음 시작점 갱신
				distance += dp[s][dust_permutate[i]];
			}
			s = dust_permutate[i];	// 현재의 먼지 인덱스는 다음의 s
		}
		if (ans > distance)
			ans = distance;
		return;
	}
	for(register int i = 0; i < total_dust_count; ++i)
		if (!check_dust[i]) {
			check_dust[i] = true;
			dust_permutate[dust_count] = i + 1;		// 먼지 인덱스 순열
			dfs(dust_count + 1, total_dust_count);
			check_dust[i] = false;
			dust_permutate[dust_count] = 0;
		}
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
	dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
	while (1) {
		cin >> W >> H;
		if (W == 0 && H == 0)
			break;
		register int total_dust_count = 0;
		for (register int h = 1, w; h <= H; ++h)
			for (w = 1; w <= W; ++w) {
				cin >> arr[h][w];
				if (arr[h][w] == 'o')
					SX = h, SY = w;
				else if (arr[h][w] == '*') {
					++total_dust_count;
					dusts[total_dust_count].first = h, dusts[total_dust_count].second = w;
				}
			}
		ans = static_cast<int>(1e8);
		memset(check_dust, false, sizeof(check_dust));
		memset(dp, 0, sizeof(dp));
		dfs(0, total_dust_count);
		cout << ans << "\n";
	}
	return 0;
}
// *&)*@*

 

1. 구글링을 하지않고 혼자서 끝까지 해결하려다보니 문제를 푸는데 굉장히 시간이 오래 걸렸습니다.
2. 저는 순열과 dp를 이용했습니다.
3. 청소기의 위치에서 먼지1, 먼지2, 먼지3 이 있다고 했을때, 청소기->먼지1->먼지2->먼지3 | 청소기->먼지1->먼지3->먼지2 | 청소기->먼지2->먼지1->먼지3 | ... 의 모든 경로의 길이를 구하고 그 중 가장 작은 값을 출력합니다.
4. 이때 예로 먼지1->먼지2 의 경로 길이를 항상 bfs로 구한다면 시간 초과 판정을 받게 됩니다.
5. 먼지1->먼지2 인 경우는 dp에 삽입했습니다. (먼지1->먼지2 와 먼지2->먼지1 의 경로 길이는 같으므로 같이 갱신하였습니다.)
6. 따라서 이후 먼지1->먼지2 가 경로에 존재하는 경우, bfs로 구하는 것이 아니라 이전의 dp값을 이용하였습니다.
7. dp는 2차원 배열로 [시작점][도착점] 의 형태입니다. 시작점은 x,y 이지만 이를 1차원 배열로 생각했습니다. (먼지1이 (3,3)에 존재하지만 먼지1은 1차원 배열로 보자면 [1] 이라고 고려했습니다.)