4991 / 로봇 청소기

로봇 청소기 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	226	59	40	32.787%

문제

오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.

방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다.

일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다. 

로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다.

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

입력

입력은 여러 개의 테스트케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 방의 가로 크기 w와 세로 크기 h가 주어진다. (1 ≤ w, h ≤ 20) 둘째 줄부터 h개의 줄에는 방의 정보가 주어진다. 방의 정보는 4가지 문자로만 이루어져 있으며, 각 문자의 의미는 다음과 같다.

• .: 깨끗한 칸
• *: 더러운 칸
• x: 가구
• o: 로봇 청소기의 시작 위치

더러운 칸의 개수는 10개를 넘지 않으며, 로봇 청소기의 개수는 항상 하나이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최소값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.

---

처음에는 로봇 청소기부터 시작해서 그냥 제일 가까운 순으로 BFS로 타고 가면 되는줄 알았는데

계속 틀렸다고 떴다. 그러고보니 생각해보면 로봇청소기랑 제일 가까운데로 갔다가 그 다음이 제일 길면?

그렇다. 다시 생각해보니 MST랑 비슷한 문제였던 것 같다. 그래서 비슷하게 한 번 구성해봤다.

구성은 다음과 같이 했다.

[1]

로봇 청소기는 0번으로 두고, 나머지 먼지들을 발견할 때마다 번호를 붙여준다. 

예를 들어 먼지가 3개라고 하면

0 : 로봇 청소기

1, 2, 3 : 먼지

이 인덱스를 기반으로 맵 자체를 바꿔버리면 x표시에 막히는 부분을 구현하기 힘들것 같아서 check라는 배열을 또 만들었다.

그래서 check 배열로 인덱싱한 위치를 표시했다. BFS를 쓰기 위함이다.

.0...1.

....2..

3......

[2]

0번째부터 BFS를 돌리면서 각 먼지까지의 거리를 dis 배열에 담아준다.

이 과정이 MST에서 노드 간 간선의 가중치를 주는 부분이라고 생각하면 된다.

여기서 잠깐, 0번째에서 1,2,3번째를 구했으면 1번째 인덱스에서 나머지를 돌 때 0과 1 사이의 거리는 이미 체크 했기 때문에 또 볼 필요가 없다.

즉, 0이면 1,2,3 사이의 거리를, 1이면 2,3 사이의 거리를, 2라면 3과의 거리를 구해서 dis배열에 대각선을 기준으로 대칭배열 하면 된다.

[3]

이렇게 하면 노드와 간선의 관계로 변경된다. 여기서 그냥 dfs돌려서 가장 최소치 찾으면 된다.

사실 여기서 정답이 나오긴 했다. 근데 127MS뜨길래 뭔가 시간을 줄일 방법을 생각해봤다.

그렇다. 맨 처음에 로봇 청소기가 청소를 끝냈을 때 기록한 최소 경로의 값이 저장돼있을 테지.(cnt_sum이 그거다)

근데 dfs를 돌면서 cnt_sum보다 큰 값으로 커진다면 굳이 가지 뻗어서 내려갈 필요가 있나? 싶었다.

그래서 그 부분을 처리해주니까 107MS나 줄어들었다.

말이 주저리 주저리 많았는데 간단히 정리하면

1. 로봇 청소기랑 더러운 부분에 번호를 붙인다.

2. 만약 로봇 청소기와 더러운 부분을 합쳐서 총 4개의 인덱스가 있다면 4개의 점 모두 BFS 돌려서 각 인덱스간의 거리를 구해서 dis 배열에 저장한다.

3. 그럼 이제 그 결과값으로 조합을 짜서 dis배열을 타고 값을 계속 누적해나간다. 중간에 최소값(cnt_sum)보다 커지면 dfs를 더 돌지 않고 넘어간다.

결론은 BFS로 배열 만들어서 DFS돌리면 되는데 최적화가 필요하다.

DFS로 완탐돌려서 최적화를 하는 부분 보고 SWEA의 [보호필름]의 해결 아이디어랑 같다는 생각이 들었다.

모처럼 낑낑대고 푼 문제였다. 이제 코드 올리고 자야겠다.

[Code]

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<algorithm>
#define P pair<int,int>
#define PI pair<P,int>
#define mp(a,b) make_pair(a,b)
#define mp3(a,b,c) mp(mp(a,b),c)
using namespace std;
 
int w, h, star, last_x, last_y, xx[] = { -1,0,1,0 }, yy[] = { 0,-1,0,1 }, check[21][21], cnt_sum = TMP_MAX, idx_tracer[21];
char map[21][21];
bool visit[21][21], flag;
 
vector<PI> contents;
 
int dis[21][21];
 
void bfs(int, int, int);
 
inline bool cmp(PI a, PI b) {
    return a.first.first < b.first.first;
}
 
void dfs(int,int,int);
 
int main() {
 
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    while (1) {
        cin >> h >> w;
 
        if (!(h|w)) break;
 
        for (int i = 0; i < w; i++) {
            cin >> map[i];
            for (int j = 0; j < h; j++) {
                if (map[i][j] == 'o') {
                    last_x = i, last_y = j;
                    check[i][j] = 0;
                    contents.push_back(mp3(0, i, j));
                }
                else if (map[i][j] == '*') {
                    check[i][j] = ++star;
                    contents.push_back(mp3(star, i, j));
                }
            }
        }
 
        // 0번째에 로봇 놓고 나머지 정렬.
        sort(contents.begin(), contents.end(), cmp);
 
        // 로봇부터 bfs돌아서 자기보다 작은 숫자만 빼고 전부 거리 측정.
 
        for (int i = 0; i < contents.size(); i++) {
            bfs(i, contents[i].first.second, contents[i].second);
            memset(visit, 0, sizeof(visit));
        }
 
        dfs(0,0,0);
        
        if (!flag) cnt_sum = -1;
        cout << cnt_sum << endl;
 
        cnt_sum = TMP_MAX, star = last_x = last_y = 0;
        contents.clear();
        memset(check, 0, sizeof(check));
        memset(dis, 0, sizeof(dis));
        flag = false;
    }
    return 0;
}
 
void bfs(int idx, int x, int y) {
    queue<PI> Q;
    Q.push(mp3(x, y, 0));
    visit[x][y] = true;
 
    while (!Q.empty()) {
        int cx = Q.front().first.first;
        int cy = Q.front().first.second;
        int cnt = Q.front().second;
        Q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = cx + xx[i];
            int ny = cy + yy[i];
            if (nx < 0 || ny < 0 || nx > w - 1 || ny > h - 1 
                || visit[nx][ny] || map[nx][ny] == 'x') continue;
 
            // 자기보다 큰 별 발견. idx행 check[nx][ny]열에 cnt를 할당한다.
            if (check[nx][ny] > idx) {
                int from = idx, to = check[nx][ny];
                dis[from][to] = dis[to][from] = cnt + 1;
            }
            visit[nx][ny] = true;
            Q.push(mp3(nx, ny, cnt + 1));
        }
    }
 
}
 
void dfs(int last_idx, int sum, int cnt) {
    if (cnt == star) {
        cnt_sum = cnt_sum > sum ? sum : cnt_sum;
        flag = true;
        return;
    }
 
    for (int i = 1; i < star + 1; i++) {
        if (!idx_tracer[i]) {
            if (dis[last_idx][i] == 0) continue;
            idx_tracer[i] = true;
            int next_sum = sum + dis[last_idx][i];
            if(next_sum < cnt_sum) dfs(i, sum + dis[last_idx][i], cnt + 1);
            idx_tracer[i] = false;
        }
    }
}