[백준 - 4991] 로봇 청소기 - C++

문제: 백트래킹, BFS, 시뮬레이션 /

 

문제

문제 링크

문제 설명

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

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

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

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

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

입력

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

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

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

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

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

출력

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

 

풀이

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX_DIST = 40000;

struct xy {int x, y;};
int w, h, len;
char board[20][20];
int dist[11][20][20];
xy dust[11], s;
queue<xy> Q;
xy dxy[] = {{1,0}, {-1,0}, {0,1}, {0,-1}};

void bfs(int idx) {
    for(int x=0; x<h; x++)
        for(int y=0; y<w; y++)
            dist[idx][x][y] = MAX_DIST;
    Q.push(dust[idx]);
    dist[idx][dust[idx].x][dust[idx].y] = 0;
    while(not Q.empty()) {
        const auto [x, y] = Q.front(); Q.pop();
        for(const auto [dx, dy]:dxy) {
            int nx = x + dx, ny = y + dy;
            if(nx<0 or nx>=h or ny<0 or ny>=w) continue;
            if(board[nx][ny] == 'x') continue;
            if(dist[idx][nx][ny] != MAX_DIST) continue;
            dist[idx][nx][ny] = dist[idx][x][y] + 1;
            Q.push({nx, ny});
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    while(true) {
        len = 0;
        cin >> w >> h;
        if(w == 0 and h == 0) break;
        for(int x=0; x<h; x++) {
            for(int y=0; y<w; y++) {
                cin >> board[x][y];
                if(board[x][y] == 'o') s = {x, y};
                else if(board[x][y] == '*') dust[len++] = {x, y};
            }
        }
        dust[len] = s;
        for(int idx=0; idx<=len; idx++) bfs(idx);
        
        int order[len+1];
        for(int i=0; i<=len; i++) order[i] = i;

        int ans = MAX_DIST;
        do {
            int d = 0;
            for(int from=len, to=0; to<len and d<ans; from=to++)
                d += dist[order[from]][dust[order[to]].x][dust[order[to]].y];
            
            ans = min(ans, d);
        } while(next_permutation(order, order+len));
        cout << (ans < MAX_DIST ? ans : -1) << '\n';
    }
}

[백준 - 17244] 아맞다우산 문제와 같은 문제

다른 점이라면 종료 점이 없다. 시뮬레이션 문제에서 제약조건이 줄어 자유도가 높아지면 더 쉬워지는 것 같다. (근데 왜 이 문제가 티어가 더 높은거지?)

 

1. 각 점을 시작으로 모든 격자점에 거리를 구한다. (이 중 먼지가 있는 점만 상용된다)
2. 먼지가 있는 점으로만 그래프를 축소하고 완전탐색으로 최소 거리 계산 (백트래킹, next_permutation() 등으로 완전탐색)