4991번 로봇 청소기

어렵지만 얻어갈 것이 많다.

1. vector 사용법에 대해서 제대로 복습할 수 있었다.
2. 문제를 해석하는 흐름이 배울게 많았다.
   로봇 청소기가 i[x1,y1]->j[x2,y2]로 갈 때 최소한의 거리를 d[i][j]에 저장한다. 이렇게 따로 저장해두면, 1->2->3으로 갈 때나 3->1->2으로 갈 때 중복되는 1->2의 거리를 한 번으로 줄일 수 있다. d배열을 위한 dist배열은 한 점에서 특정점으로 갈때의 최소한의 거리를 저장한다. 여기서 약간 헷갈릴 수 있는데 정리하자면, d배열의 [i][j]는 i라는 점에서 j라는 점으로 갈때이고, dist배열의 [i][j]는 한 점에서 i,j로 갈때이다.

#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <tuple>
#include <algorithm>
using namespace std;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
vector<vector<int>> bfs(vector<string>& map, int sx, int sy) {
	int x, y;
	int n = map.size();
	int m = map[0].size();
	vector<vector<int>> dist(n, vector<int>(m,-1));
	dist[sx][sy] = 0;
	queue<pair<int, int>> Q;
	Q.push(make_pair(sx, sy));
	while (!Q.empty()) {
		tie(x, y) = Q.front(); Q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
			if (map[xx][yy] == 'x') continue;
			if (dist[xx][yy] == -1) {
				dist[xx][yy] = dist[x][y] + 1;
				Q.push(make_pair(xx, yy));
			}
		}
	}
	return dist;
}

int main() {
	//freopen("in1.txt", "rt", stdin);
	int n, m;
	while (1) {
		cin >> m >> n;
		if (m == 0 && n == 0) {
			//cout << -1 << '\n';
			break;
		}
		vector<string> map(n);
		vector<pair<int,int>> b(1);
		for (int i = 0; i < n; i++) {
			cin >> map[i];
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 'o') b[0] = make_pair(i, j);
				else if (map[i][j] == '*') b.push_back(make_pair(i, j));
			}
		}
		int l = b.size();
		bool ok = true;
		vector<vector<int>> d(l, vector<int>(l));
		for (int i = 0; i < l; i++) {
			vector<vector<int>> dist = bfs(map, b[i].first, b[i].second);
			for (int j = 0; j < l; j++) {
				//if (i == j) continue;
				d[i][j] = dist[b[j].first][b[j].second];
				if (d[i][j] == -1) ok = false;
			}
		}
		if (ok == false) {
			cout << -1 << '\n';
			continue;
		}
		vector<int> p(l-1);
		for (int i = 0; i < l - 1; i++) {
			p[i] = i + 1;
		}
		int ans = -1;
		int cnt = 0;
		do {
			cnt = d[0][p[0]];
			for (int i = 0; i < l - 2; i++) {
				cnt += d[p[i]][p[i + 1]];
			}
			if (ans==-1||cnt < ans) ans = cnt;
		} while (next_permutation(p.begin(), p.end()));
		cout << ans << '\n';
	}

	return 0;
}