백준, boj) 4991. 로봇 청소기

1. 문제 링크

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

4991번: 로봇 청소기

2. 문제 개요

로봇 청소기를 사용해 청소를 하려고 한다. 경로는 유저가 직접 정할 수 있다.

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

 

3. 문제 힌트

더러운 지역의 개수가 최대 10개밖에 되지 않기 때문에 순열(permutation)을 사용해서 구현 가능하다.

DP로 푸는 것은 아마 외판원 순회 같은 유형일 것 같다.

 

(1) 출발점 및 더러운 칸 간 거리 구하기

(2) 순서를 순열로 결정하기

(3) Simulation 해보기

 

4. 문제 풀기

입력받을 때

더러운 칸을 0번부터 카운팅 한다. 0 ~ 9번이 먼지가 된다.

그리고. 인부분은 -1로, 벽인 부분은 -2로 했다. 출발지는 최대 index인 10으로 했다.

 

그리고 각 개체 간 거리를 구한다.

거리를 구할 때는 각 개체들을 시작으로 BFS를 돌려서 최단거리를 구하자.

즉, 먼지가 10개라면, 출발점을 포함해서 11번 BFS를 돌려야 한다.

 

이렇게 거리를 구하면 끝이다.

순열을 만들어서 순서를 결정지어주자.

그리고 시뮬레이션을 하고 최솟값을 구해주자

 

밑의 코드는 변수가 조금 지저분하다. 머리 쓰기 귀찮아서 그냥 인덱싱을 대충 했다.

반복문 1개로 한 번에 할 수 있는데 그냥 귀찮아서 따로따로 했다.

시간 복잡도는 개체 1개당 BFS를 1번 하므로 BFS는 O(W*H)이고 N개 있다.

그리고 더러운 곳이 N 개라면 N! 시뮬레이션은 그냥 간단한 반복문이니 패스.

O(WHN + N!)이 되겠다.

 

5. 코드

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

int n, m;
const int dx[] = { 1,-1,0,0 };
const int dy[] = { 0,0,1,-1 };
int order[11];
int used[11] = { 1,1,1,1,1,1,1,1,1,1,1 };
int srcindex = 10;
int ans = 987654321;

struct COORD {
	int y, x;
	int d;
};


void dfs(int depth, int dirnum,int dist[11][11])
{
	if (depth == dirnum) {
		int ret = 0;

		//src - dir;
		ret += dist[srcindex][order[0]];

		for (int i = 1; i < dirnum; ++i) 
			ret += dist[order[i - 1]][order[i]];
		
		ans = min(ans, ret);
		return;
	}


	for (int i = 0; i < dirnum; ++i) {
		if (used[i] != 0) {
			order[depth] = i;
			used[i]--;
			dfs(depth + 1, dirnum, dist);
			used[i]++;
		}
	}
	return;
}

int main()
{
	scanf("%d %d", &m, &n);

	while (!(m == 0 && n == 0)) {
		
		//init
		int map[20][20] = { 0 };
		int dirnum = 0;
		ans = 987654321;

		pair<int, int> src;
		vector<pair<int, int>> dirty;

		int dist[11][11];	//dirty 0 ~ 9, src : 10
		
		for (int i = 0; i < 11; ++i)
			for (int j = 0; j < 11; ++j)
				dist[i][j] = 987654321;
		
		bool visited[20][20] = { false, };

		//input
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				scanf("%c", &map[i][j]);

				if (map[i][j] == '\n') 
					j--;
				if (map[i][j] == '.')
					map[i][j] = -1;

				if (map[i][j] == 'x')
					map[i][j] = -2;
				
				if (map[i][j] == 'o') {
					map[i][j] = srcindex;
					src.first = i; src.second = j;
				}
				
				if (map[i][j] == '*') {
					map[i][j] = dirnum++;
					dirty.push_back({ i,j });
				}
			}
		}

		//src - dirty 
		queue<COORD> q;

		COORD init;
		init.y = src.first;
		init.x = src.second;
		init.d = 0;

		q.push(init);
		visited[src.first][src.second] = true;

		while (!q.empty()) {
			COORD cur = q.front(); q.pop();

			if (map[cur.y][cur.x] != -1) {
				dist[srcindex][map[cur.y][cur.x]] = cur.d;
				dist[map[cur.y][cur.x]][srcindex] = cur.d;
			}
			
			for (int dir = 0; dir < 4; ++dir) {
				COORD next;
				next.y = cur.y + dy[dir];
				next.x = cur.x + dx[dir];
				next.d = cur.d + 1;

				if (next.x < 0 || next.y < 0 || next.x >= m || next.y >= n || map[next.y][next.x]== -2 || visited[next.y][next.x])
					continue;

				visited[next.y][next.x] = true;
				q.push(next);
			}
		}
		
		//먼지 간 거리
		for (int i = 0; i < dirnum; ++i) {
			memset(visited, false, sizeof(visited));

			queue<COORD> q;

			COORD init;
			init.y = dirty[i].first;
			init.x = dirty[i].second;
			init.d = 0;

			q.push(init);
			visited[dirty[i].first][dirty[i].second] = true;

			while (!q.empty()) {
				COORD cur = q.front(); q.pop();

				if (map[cur.y][cur.x] != -1) {
					dist[i][map[cur.y][cur.x]] = cur.d;
					dist[map[cur.y][cur.x]][i] = cur.d;
				}

				for (int dir = 0; dir < 4; ++dir) {
					COORD next;
					next.y = cur.y + dy[dir];
					next.x = cur.x + dx[dir];
					next.d = cur.d + 1;

					if (next.x < 0 || next.y < 0 || next.x >= m || next.y >= n || map[next.y][next.x] == -2 || visited[next.y][next.x])
						continue;

					visited[next.y][next.x] = true;
					q.push(next);
				}
			}
		}

		bool check = true;

		//check dist
		for (int i = 0; i < dirnum; ++i)
			if (dist[srcindex][i] == 987654321) {
				check = false;
				ans = -1;
			}

		//permutation
		if(check)
			dfs(0, dirnum, dist);

		printf("%d\n", ans);

		scanf("%d %d", &m, &n);
	}
	return 0;
}

6. 결과 사진