백준 4991번: 로봇 청소기 (Java)

문제

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

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

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

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

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

입력

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

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

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

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

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

출력

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

 

---

 

풀이

최대 10개의 먼지가 있으므로, 브루트포스 방법으로 다 따져봐도 10! = 362만개의 경우가 있다. 다만 테스트케이스의 개수(문제에서 제시해주지 않았다)에 따라 TLE가 나올 수도 있으나, 일단은 안 나왔으니 틀린 풀이는 아니라 생각한다.

주어진 지도를 살짝 다르게 표현하자: 깨끗한 칸을 -1, 시작점을 0, 먼지를 1~dustNum, 가구를 1억으로 이차원 int 배열 'map'에 표현한다.

이차원 int 배열 dist를 다음과 같이 나타내자: dist[s][e] := (s에서 e로 가는 최단 거리).

map에서 bfs를 1+dustNum번 돌아 각 점에서 다른 점까지의 최단 거리를 dist에 기록해준 후, 브루트포스로 뽑은 모든 경로에 대회 최단 경로를 찾으면 된다.

 

배울 점

TSP로 푸는 게 더 효율적인 풀이 방법인 듯하다. 2098번 외판원 순회랑 비교했을 때, 본 문제가 구현 처리가 살짝 있는 반면 먼지의 개수가 10개 이하이다. 외판원 순회는 최대 16개의 점을 방문해야하므로 브루트포스 풀이는 확실하게 TLE가 뜰 것이다. 나중에 시간이 될 때 위 문제를 풀어보도록 하자.

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };
    static int[][] map, loc, dist;
    static boolean[] checked; // 백트래킹 시 방문 체크를 위한 boolean 배열
    static int M, N, dustNum, ans;
    static final int INF = 100_000_000;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        while (M != 0) {
            map = new int[M][N];
            dustNum = 0;
            ans = INF;
            for (int i = 0; i < M; i++) {
                String str = br.readLine();
                for (int j = 0; j < N; j++) {
                    char cur = str.charAt(j);
                    if (cur == '.') {
                        map[i][j] = -1;
                    } else if (cur == 'o') {
                        map[i][j] = 0;
                    } else if (cur == 'x') {
                        map[i][j] = INF;
                    } else {
                        map[i][j] = ++dustNum;
                    }
                }
            }
            checked = new boolean[dustNum+1];
            loc = new int[1+dustNum][2]; // 로봇청소기, 먼지의 위치 기록
            // dist[s][e]: s에서 e로 가는 최단 거리
            dist = new int[1+dustNum][1+dustNum]; 
            for (int i = 0; i <= dustNum; i++) {
                Arrays.fill(dist[i], INF);
            }
            
            for (int i = 0; i < M; i++) {
                for (int j = 0; j < N; j++) {
                    if (map[i][j] >= 0 && map[i][j] <= dustNum) {
                        loc[map[i][j]][0] = i;
                        loc[map[i][j]][1] = j;
                    }
                }
            }
            
            // 0번 먼지(==청소기)부터 dustNum번 먼지가 다른 곳까지 가는 최단 경로 찾기
            for (int i = 0; i <= dustNum; i++) {
                bfs(i);
            }
            
            perm(0, 0, 0);
            if (ans == INF) System.out.println(-1);
            else System.out.println(ans);
            
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
        }
    }
    
    // start번 먼지에서 0~dustNum번 먼지까지 가는 최단 경로를 찾는 method
    static void bfs(int start) {
        boolean[][] visited = new boolean[M][N];
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(loc[start]);
        visited[loc[start][0]][loc[start][1]] = true;
        int d = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            d++;
            while (size-- > 0) {
                int[] cur = queue.poll();
                int r = cur[0], c = cur[1];
                for (int i = 0; i < 4; i++ ) {
                    int nr = r + dr[i], nc = c + dc[i];
                    if (nr < 0 || nr >= M || nc < 0 || nc >= N) continue;
                    if (visited[nr][nc] || map[nr][nc] == INF) continue;
                    visited[nr][nc] = true;
                    queue.offer(new int[] {nr, nc});
                    if (map[nr][nc] >= 0 && map[nr][nc] <= dustNum) {
                        dist[start][map[nr][nc]] = d;
                    }
                }
            }
        }
    }
    
    // 모든 경로에 대해 경로의 길이를 구하는 method
    static void perm(int cnt, int cur, int temp) {
        if (cnt == dustNum) {
            ans = Math.min(ans, temp);
            return;
        }
        
        for (int nxt = 1; nxt <= dustNum; nxt++) {            
            if (checked[nxt]) continue;
            checked[nxt] = true;
            perm(cnt+1, nxt, temp+dist[cur][nxt]);
            checked[nxt] = false;
        }
    }    
}