BOJ 4991 - 로봇 청소기

4991번: 로봇 청소기

 

방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값

우선 같은 칸을 여러 번 방문할 수 있다는 점을 주의해야 한다.

즉 노드를 기준으로 방문처리를 하면 안 된다. 그럼 어떻게 방문 처리를 할까?

간선을 만들고 이때 모든 점을 연결하지 못한다면 -1이다.

모든 지점 간의 거리를 계산해서 간선과 코스를 구한다.

노드 간의 최단거리 즉 간선을 어떻게 구할까? → 노드별로 bfs를 통해서 처리한다.

그 후 어떤 방식으로 간선을 선택할까?

크루스칼 알고리즘이 떠오른다. 하지만 이 문제는 출발점이 명확하고 크루스칼로 가장 비용이 적은 그래프를 만들어도 왔다 갔다 하는 경우가 발생해 최소 비용이 안된다.

결국 모든 경우의 수를 다 따져야 한다.

1. 노드 간 최단 거리를 구해 저장한다.
2. 더러운 칸 노드를 순열로 순서를 정한다.
3. 시작점부터 순서대로 이동하는 거리의 합을 구해 최솟값을 갱신한다.

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Dictionary;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ4991 {

    static FastReader scan = new FastReader();
    static final int[][] DIRECTION = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static int W, H;
    static int[][] map;
    static int[] start;
    static Map<Integer, int[]> nodes;
    static int MIN;

    static int[][] calculateDistance() {
        int n = nodes.size();
        int[][] distances = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(distances[i], -1);
        }
        for (int start = 1; start <= nodes.size(); start++) {
            Queue<int[]> q = new LinkedList<>();
            boolean[][] visited = new boolean[H][W];
            int[] node = nodes.get(start);
            q.add(new int[]{node[0], node[1], 0});
            visited[node[0]][node[1]] = true;

            while (!q.isEmpty()) {
                int[] curr = q.poll();
                int r = curr[0];
                int c = curr[1];
                int cost = curr[2];

                if (map[r][c] > 0) {
                    distances[start][map[r][c]] = cost;
                    distances[map[r][c]][start] = cost;
                }

                for (int d = 0; d < 4; d++) {
                    int nr = r + DIRECTION[d][0];
                    int nc = c + DIRECTION[d][1];

                    if (!inRange(nr, nc)) continue;
                    if (map[nr][nc] == -1) continue;
                    if (visited[nr][nc]) continue;

                    q.add(new int[]{nr, nc, cost + 1});
                    visited[nr][nc] = true;
                }
            }
        }

        return distances;
    }

    static boolean inRange(int r, int c) {
        return r >= 0 && r < H && c >= 0 && c < W;
    }

    static void solve() {
        int[][] distances = calculateDistance();
        int n = nodes.size();
        permutate(0, n - 1, new int[n - 1], new boolean[n + 1], distances);
        System.out.println(MIN == Integer.MAX_VALUE ? -1 : MIN);
    }

    static void permutate(int depth, int n, int[] selected, boolean[] visited, int[][] distances) {
        if (depth == n) {
            int distance = 0;
            int start = 1;
            for (int node : selected) {
                if (distances[start][node] == -1) {
                    return;
                }
                distance += distances[start][node];
                start = node;
            }
            MIN = Math.min(MIN, distance);
            return;
        }

        for (int i = 2; i <= n + 1; i++) {
            if (visited[i]) continue;
            selected[depth] = i;
            visited[i] = true;
            permutate(depth + 1, n, selected, visited, distances);
            selected[depth] = 0;
            visited[i] = false;
        }
    }

    public static void main(String[] args) {
        while (true) {
            MIN  = Integer.MAX_VALUE;
            W = scan.nextInt();
            H = scan.nextInt();
            if (W == 0 && H == 0) {
                return;
            }
            map = new int[H][W];
            nodes = new HashMap<>();
            int id = 1;
            for (int i = 0; i < H; i++) {
                char[] row = scan.next().toCharArray();
                for (int j = 0; j < W; j++) {
                    if (row[j] == 'o') {
                        map[i][j] = 1; // 시작점
                        start = new int[]{i, j};
                        nodes.put(1, start);
                    } else if (row[j] == '*') {
                        map[i][j] = ++id; // 더러운 칸 노드
                        nodes.put(id, new int[]{i, j});
                    } else if (row[j] == 'x') {
                        map[i][j] = -1; // 이동 불가능 칸
                    }
                }
            }

            solve();
        }
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}