[BOJ] 4991 : 로봇 청소기
풀이
BFS
처음생각보다 훨씬 어려웠던 문제.
단순히 가까운점 부터 탐색을 시키니 최소를 보장 할 수 없는 문제가 생겼다.
( * o * * ) 대충 이럴경우 조금 더 거리가 먼 왼쪽부터 먹고 오른쪽으로 향하는게 더 빠르다.
배열에 메모이제이션해놓고 거리를 먼저 다 구해준다음에 next_permutation으로 조합을 짜서 풀었다.
그런데 이때 그냥 대충 o(시작점)도 *로 바꾸고 풀었더니 경로가 꼬이는 문제가 있었다.
그래서 vector<pair<int, int» dirt(1) 를 하고, 시작점이면 dirt[0] = make_pair(i, j)
아닐경우 dirt.push_back({i,j}) 를 하는 방법을 사용했다. (백준님 코드 참고함)
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };
int w, h;
string map[20];
//dist[a][b] : a->b distance
int dist[11][11];
void bfs(int idx, vector<pair<int, int>> &dirt) {
int chk[20][20] = { 0 };
queue<pair<pair<int, int>, int>> q;
q.push({ {dirt[idx].first,dirt[idx].second} ,0 });
chk[dirt[idx].first][dirt[idx].second] = 1;
while (!q.empty()) {
int x = q.front().first.first;
int y = q.front().first.second;
int d = q.front().second;
q.pop();
if (map[x][y]=='*') {
for (int i = 0; i < dirt.size(); i++) {
if (dirt[i].first == x && dirt[i].second == y) {
dist[idx][i] = d;
break;
}
}
}
for (int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx >= 0 && nx < h&&ny >= 0 && ny < w&&map[nx][ny] != 'x' && chk[nx][ny]==0) {
chk[nx][ny] = 1;
q.push({ {nx,ny},d+1 });
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> w >> h;
while (w || h) {
memset(dist, -1, sizeof(dist));
for (int i = 0; i < h; i++) {
cin >> map[i];
}
//시작점은 0번째를 보장해야한다.
vector<pair<int, int>> dirt(1);
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (map[i][j] == 'o') {
map[i][j] = '*';
dirt[0] = make_pair(i, j);
}
else if (map[i][j] == '*') {
dirt.push_back({i,j});
}
}
}
int flag = 0;
for (int i = 0; i < dirt.size(); i++) {
bfs(i, dirt);
for (int j = 0; j < dirt.size(); j++) {
if (dist[i][j] == -1) {
flag = 1;
break;
}
}
if (flag)
break;
}
if (flag) {
cout << -1 << '\n';
}
else {
int ans = 987654321;
//점 방문 순서 조합
vector<int> num;
//시작점 빼고
for (int i = 1; i < dirt.size(); i++) {
num.push_back(i);
}
do {
int tmp = dist[0][num[0]];
for (int i = 0; i < dirt.size() - 2;i++) {
tmp += dist[num[i]][num[i + 1]];
}
if (ans > tmp) {
ans = tmp;
}
} while (next_permutation(num.begin(),num.end()));
cout << ans << '\n';
}
cin >> w >> h;
}
return 0;
}
Written on May 26, 2019