[BOJ] 4991. 로봇 청소기(BFS, 순열)

#. Problem

https://www.acmicpc.net/problem/4991

* The copyright in this matter is in BOJ

 

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

문제 길이에 비해 많은 생각이 필요했던 문제였다... .. .

"더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램" 만 봐서는

평범한 BFS 문제 같다.

하지만, 다시 보면 모두 깨끗한 칸으로 만들어야 한다고 한다.

"더러운 칸의 개수는 10개를 넘지 않으.."

"로봇은 같은 칸을 여러 번 방문할 수 있다.."

는 조건이 있어서 모든 경우의 수를 시도해보아야 한다. (브루트포스)

1.

먼저 각 정점과 정점(초기 로봇 위치 + 더러운 칸) 사이의 거리를 계산해준다.

더러운 칸의 개수가 N개라면, 모든 정점 사이의 거리를 계산하는데 최대 => O(N^2 * NM)

2.

순열을 활용해서 모두 깨끗한 칸으로 만들 수 있는 모든 경로를 시도 => O(N!)

O(N^2 * NM + N!) 에 해결할 수 있다.

#. Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ4991 {
 
    static int W, H, cntDirtyArea, map[][], answer;
    static Point[] coordinates;
    static int distances[][];
    static boolean visited[][], isSelect[];
    static Queue<Point> q;
    static int[] dr = {0, 1, 0, -1}, dc = {-1, 0, 1, 0};
    static class Point {
        int r, c;
        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
    
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        while(true) {
            
            st = new StringTokenizer(br.readLine());
            W = Integer.parseInt(st.nextToken()); // 방의 가로
            H = Integer.parseInt(st.nextToken()); // 방의 세로
            if(W == 0 && H == 0) break;
            
            map = new int[H][W];
            coordinates = new Point[11]; // 더러운 칸은 최대 10칸
            distances = new int[11][11];
            cntDirtyArea = 1;
            answer = Integer.MAX_VALUE;
            
            for (int i = 0; i < H; i++) {
                char tmp[] = br.readLine().toCharArray();
                
                for (int j = 0; j < W; j++) {
                    map[i][j] = tmp[j];
                    
                    if(map[i][j] == 'o') {
                        coordinates[0] = new Point(i, j);
                    } else if(map[i][j] == '*') {
                        coordinates[cntDirtyArea++] = new Point(i, j);
                    }
                }
            }
            
            isSelect = new boolean[cntDirtyArea];
            if(calculateDistances()) {
                cleaning(0, 0, 0);
                System.out.println(answer);
            } else {
                System.out.println(-1);
            }
        }
    }
 
    private static boolean calculateDistances() {
        for (int i = 0; i < cntDirtyArea; i++) {
            for (int j = i + 1; j < cntDirtyArea; j++) {
                int d = dist(coordinates[i], coordinates[j]);
                if(d == -1) {
                    return false;
                } else {
                    distances[i][j] = distances[j][i] = d;
                }
            }
        }
        return true;
    }
 
    private static int dist(Point start, Point end) {
        
        q = new LinkedList<>();
        visited= new boolean[H][W];
        q.add(start);
        visited[start.r][start.c] = true;
        
        int result = 0;
        while(!q.isEmpty()) {
            int size = q.size();
            ++result;
            
            while(size-- > 0) {
                Point now = q.poll();
                for (int d = 0; d < 4; d++) {
                    int rr = now.r + dr[d];
                    int cc = now.c + dc[d];
                    if(rr < 0 || cc < 0 || rr >= H || cc >= W || 
                            visited[rr][cc] || map[rr][cc] == 'x') continue;
                    if(rr == end.r && cc == end.c) return result;
                    visited[rr][cc] = true;
                    q.add(new Point(rr, cc));
                }
            }
        }
        return -1;
    }
 
    private static void cleaning(int now, int cnt, int sum) {
        if(cnt == cntDirtyArea - 1) {
            answer = Math.min(answer, sum);
            return;
        }
        
        for (int i = 1; i < cntDirtyArea; i++) {
            if(isSelect[i]) continue;
            
            isSelect[i] = true;
            cleaning(i, cnt + 1, sum + distances[now][i]);
            isSelect[i] = false;
        }
    }
}