[백준/Java] 4991 : 로봇 청소기

📌 문제 정보

• 번호: 4991
• 제목: 로봇 청소기
• 난이도: Gold 1
• 분류: 그래프 탐색, BFS, 비트마스킹, 다이나믹 프로그래밍(DP)

---

💡 접근 방식

더러운 칸을 모두 청소하는 최소 이동 횟수를 구하는 문제입니다.
더러운 칸이 최대 10개이므로, 시작점과 더러운 칸들 사이의 최단거리를 BFS로 미리 구해두고
비트마스크 DP로 모든 더러운 칸을 청소하는 최소 이동 횟수를 계산합니다.

---

🔹 1단계 – 중요 지점 수집

o를 points[0]으로, *들을 순서대로 points[1~N]에 저장

if (map[i][j] == 'o') points.add(0, new int[]{i, j});
if (map[i][j] == '*') points.add(new int[]{i, j});

---

🔹 2단계 – BFS로 지점 간 최단거리 계산

for (int i = 0; i < points.size(); i++) {
    times = bfs(points.get(i)[0], points.get(i)[1]);
    for (int j = 0; j < points.size(); j++) {
        dist[i][j] = times[points.get(j)[0]][points.get(j)[1]];
    }
}

---

🔹 3단계 – 비트마스크 DP

dp[i][mask] = points[i+1]번 더러운 칸에 있고,
              mask 상태만큼 청소했을 때 최소 이동 횟수

초기화 — o에서 각 더러운 칸으로 첫 출발

for (int i = 0; i < trashCnt; i++) {
    dp[i][1 << i] = dist[0][i + 1];
}

전이 — 현재 위치에서 아직 안 청소한 칸으로 이동

int next = mask | (1 << j);
dp[j][next] = Math.min(dp[j][next], dp[i][mask] + dist[i + 1][j + 1]);

---

🔹 4단계 – 정답 도출

for (int i = 0; i < trashCnt; i++) {
    minTime = Math.min(minTime, dp[i][(1 << trashCnt) - 1]);
}

---

💻 핵심 코드

for (int mask = 1; mask < (1 << trashCnt); mask++) {
    for (int i = 0; i < trashCnt; i++) {
        if (dp[i][mask] == Integer.MAX_VALUE) continue;

        for (int j = 0; j < trashCnt; j++) {
            if ((mask & (1 << j)) != 0) continue;
            if (dist[i + 1][j + 1] == -1) continue;

            int next = mask | (1 << j);
            dp[j][next] = Math.min(dp[j][next], dp[i][mask] + dist[i + 1][j + 1]);
        }
    }
}

---

⏳ 복잡도 분석

• 시간 복잡도: O(지점 수 × H × W + N² × 2^N)
• 공간 복잡도: O(H × W + N × 2^N)

---

📄 전체 코드

package B4991;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int W, H;
    static char[][] map;
    static int[] dr = {0, 0, 1, -1};
    static int[] dc = {1, -1, 0, 0};
    static Queue<int[]> q;
    static int[][] times;
    static List<int[]> points = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        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 char[H][W];
            q = new LinkedList<>();
            points = new ArrayList<>();

            for (int i = 0; i < H; i++) {
                String str = br.readLine();
                for (int j = 0; j < W; j++) {
                    map[i][j] = str.charAt(j);
                    if (map[i][j] == 'o') points.add(0, new int[]{i, j});
                    if (map[i][j] == '*') points.add(new int[]{i, j});
                }
            }

            int trashCnt = points.size() - 1;
            int[][] dist = calcDist();

            if (isImpossible(dist)) {
                sb.append(-1).append("\n");
                continue;
            }

            int minTime = solve(dist, trashCnt);
            sb.append(minTime).append("\n");
        }
        System.out.print(sb);
    }

    static int[][] calcDist() {
        int[][] dist = new int[points.size()][points.size()];
        for (int[] row : dist) Arrays.fill(row, -1);

        for (int i = 0; i < points.size(); i++) {
            times = bfs(points.get(i)[0], points.get(i)[1]);
            for (int j = 0; j < points.size(); j++) {
                dist[i][j] = times[points.get(j)[0]][points.get(j)[1]];
            }
        }
        return dist;
    }

    static boolean isImpossible(int[][] dist) {
        for (int i = 1; i < points.size(); i++) {
            if (dist[0][i] == -1) return true;
        }
        return false;
    }

    static int solve(int[][] dist, int trashCnt) {
        int[][] dp = new int[trashCnt][1 << trashCnt];
        for (int[] cell : dp) Arrays.fill(cell, Integer.MAX_VALUE);

        for (int i = 0; i < trashCnt; i++) {
            dp[i][1 << i] = dist[0][i + 1];
        }

        for (int mask = 1; mask < (1 << trashCnt); mask++) {
            for (int i = 0; i < trashCnt; i++) {
                if (dp[i][mask] == Integer.MAX_VALUE) continue;

                for (int j = 0; j < trashCnt; j++) {
                    if ((mask & (1 << j)) != 0) continue;
                    if (dist[i + 1][j + 1] == -1) continue;

                    int next = mask | (1 << j);
                    dp[j][next] = Math.min(dp[j][next], dp[i][mask] + dist[i + 1][j + 1]);
                }
            }
        }

        int minTime = Integer.MAX_VALUE;
        for (int i = 0; i < trashCnt; i++) {
            minTime = Math.min(minTime, dp[i][(1 << trashCnt) - 1]);
        }
        return minTime == Integer.MAX_VALUE ? -1 : minTime;
    }

    static int[][] bfs(int sr, int sc) {
        times = new int[H][W];
        for (int[] time : times) Arrays.fill(time, -1);

        q = new LinkedList<>();
        times[sr][sc] = 0;
        q.add(new int[]{sr, sc});

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

            for (int dir = 0; dir < 4; dir++) {
                int nr = r + dr[dir];
                int nc = c + dc[dir];

                if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
                if (map[nr][nc] == 'x') continue;
                if (times[nr][nc] != -1) continue;

                times[nr][nc] = times[r][c] + 1;
                q.add(new int[]{nr, nc});
            }
        }
        return times;
    }
}