백준 - 로봇 청소기 (4991)

1. 문제

문제 링크

2. 풀이

1. 방에서 방으로 이동하는 거리를 모두 구해서 dist배열에 저장
2. 더러운 방을 청소하러 가는 순서의 모든 경우의 수 만들기
3. 청소하러 가기

이렇게 세 단계로 나누어 풀 수 있습니다.

3. 전체 코드

#define MAX 20
#define INF 50000
#include <bits/stdc++.h>

using namespace std;

int w, h;
int dirtyCount;
int robotY, robotX;
int my[4] = { -1, 0, 1, 0 };
int mx[4] = { 0, 1, 0, -1 };
int used[10];
char room[MAX][MAX];
int visited[MAX][MAX];
int dist[MAX][MAX][MAX][MAX];
queue<pair<int, int>> q, rq;
vector<pair<int, int>> dirties;
pair<int, int> per[11];

int slove(int depth) {
	if (depth == dirties.size()) {
		int ret = 0;

		for (int i = 1; i <= dirties.size(); i++) {
			int sy = per[i - 1].first;
			int sx = per[i - 1].second;
			int ty = per[i].first;
			int tx = per[i].second;

			ret += dist[sy][sx][ty][tx];
		}

		return ret;
	}

	int ret = INF;

	for (int i = 0; i < dirties.size(); i++) {
		if (used[i]) continue;

		used[i] = 1;
		per[depth + 1] = dirties[i];
		ret = min(ret, slove(depth + 1));
		used[i] = 0;
	}

	return ret;
}

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

	while (1) {
		cin >> w >> h;

		if (w == 0 && h == 0) break;

		int idx = 1;

		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> room[i][j];

				if (room[i][j] == 'o') {
					per[0].first = i;
					per[0].second = j;
				}
				else if (room[i][j] == '*') {
					per[idx].first = i;
					per[idx++].second = j;
					dirties.push_back({ i, j });
				}

				visited[i][j] = -1;
			}
		}

		int isBlocked = 0;

		// 이동하는 모든 경우의 거리 저장하기
		for (int i = 0; i < dirties.size() + 1; i++) {
			for (int j = i + 1; j < dirties.size() + 1; j++) {
				int sy = per[i].first;
				int sx = per[i].second;
				int ty = per[j].first;
				int tx = per[j].second;
				int isCleaned = 0;

				q.push({ sy, sx });
				visited[sy][sx] = 0;

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

					rq.push(q.front());
					q.pop();

					for (int dir = 0; dir < 4; dir++) {
						int ny = y + my[dir];
						int nx = x + mx[dir];

						if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue;

						if (room[ny][nx] == 'x') continue;

						if (visited[ny][nx] != -1) continue;

						// 목표 지점을 찾았을 때
						if (ny == ty && nx == tx) {
							dist[sy][sx][ty][tx] = visited[y][x] + 1;
							dist[ty][tx][sy][sx] = visited[y][x] + 1;
							isCleaned = 1;
							break;
						}

						q.push({ ny, nx });
						visited[ny][nx] = visited[y][x] + 1;
					}

					if (isCleaned) break;
				}

				// visited 초기화
				while (!q.empty()) {
					rq.push(q.front());
					q.pop();
				}

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

					visited[y][x] = -1;
					rq.pop();
				}

				if (!isCleaned) {
					isBlocked = 1;
					break;
				}
			}

			// 막혔으면 루프 종료
			if (isBlocked) break;
		}

		cout << (isBlocked ? -1 : slove(0)) << '\n';

		// dist 초기화
		for (int i = 0; i < dirties.size() + 1; i++) {
			for (int j = i + 1; j < dirties.size() + 1; j++) {
				int sy = per[i].first;
				int sx = per[i].second;
				int ty = per[j].first;
				int tx = per[j].second;

				dist[sy][sx][ty][tx] = 0;
				dist[ty][tx][sy][sx] = 0;
			}
		}

		dirties.clear();
	}

	return 0;
}