[BOJ/Java] 4991. 로봇 청소기

📌 [BOJ/Java] 4991. 로봇 청소기

🔗 문제 링크: 백준 4991번 - 로봇 청소기

---

📖 문제 해석

🧹 W × H 크기의 방에서 로봇 청소기가 모든 먼지(*)를 청소해야 한다.
🚧 장애물(x)을 피하면서 최소 이동 거리를 찾아야 한다.
🎯 모든 먼지를 최단 거리로 방문하는 최소 이동 횟수를 구하는 문제

✅ 핵심 개념

• BFS로 각 지점 간 최단 거리 계산
• 비트마스킹 DP로 최적의 방문 순서 찾기 (TSP 응용)

---

🛠️ 풀이 과정

1️⃣ 입력 처리 및 초기화

• W × H 크기의 맵 입력받기
• 로봇(o)과 먼지(*) 좌표 저장
• 모든 먼지 간 최단 거리 계산(BFS)

2️⃣ 모든 지점 간 최단 거리 계산 (BFS)

• dist[i][j]: i번 먼지에서 j번 먼지까지의 최단 거리
• 도달할 수 없는 경우 -1 반환

3️⃣ 비트마스킹 DP(TSP 방식)

• dp[mask][i] → 현재 mask 상태에서 i번 먼지까지 가는 최소 이동 거리
• mask | (1 << j) → j번 먼지를 추가 방문한 상태
• dp[nextMask][j] = min(dp[nextMask][j], dp[mask][i] + dist[i][j])

---

💻 코드 구현 (Java)

import java.util.*;

public class Main {
    static class Point {
        int x, y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static int W, H, dustCount;
    static char[][] map;
    static int[][] dist;
    static Point[] dusts;
    static int[][] dp;
    static int[] dx = { -1, 1, 0, 0 }; // 상, 하, 좌, 우
    static int[] dy = { 0, 0, -1, 1 };

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (true) {
            W = sc.nextInt();
            H = sc.nextInt();
            if (W == 0 && H == 0) break;

            map = new char[H][W];
            dusts = new Point[11]; // 최대 먼지 개수 (10) + 로봇 (1)
            dustCount = 1;

            for (int i = 0; i < H; i++) {
                String line = sc.next();
                for (int j = 0; j < W; j++) {
                    map[i][j] = line.charAt(j);
                    if (map[i][j] == 'o') dusts[0] = new Point(i, j);
                    else if (map[i][j] == '*') dusts[dustCount++] = new Point(i, j);
                }
            }

            dist = new int[dustCount][dustCount]; // 모든 먼지 간 거리

            boolean reachable = true;
            for (int i = 0; i < dustCount; i++) {
                if (!bfs(i)) {
                    reachable = false;
                    break;
                }
            }

            if (!reachable) {
                System.out.println(-1);
                continue;
            }

            dp = new int[1 << dustCount][dustCount];
            for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
            dp[1][0] = 0; // 로봇 위치에서 시작

            System.out.println(tsp());
        }
    }

    public static boolean bfs(int start) {
        Queue<Point> q = new LinkedList<>();
        boolean[][] visited = new boolean[H][W];
        int[][] tempDist = new int[H][W];

        q.offer(dusts[start]);
        visited[dusts[start].x][dusts[start].y] = true;

        while (!q.isEmpty()) {
            Point cur = q.poll();
            for (int d = 0; d < 4; d++) {
                int nx = cur.x + dx[d];
                int ny = cur.y + dy[d];

                if (nx < 0 || ny < 0 || nx >= H || ny >= W || visited[nx][ny] || map[nx][ny] == 'x') continue;

                visited[nx][ny] = true;
                tempDist[nx][ny] = tempDist[cur.x][cur.y] + 1;
                q.offer(new Point(nx, ny));
            }
        }

        for (int i = 0; i < dustCount; i++) {
            int x = dusts[i].x, y = dusts[i].y;
            dist[start][i] = visited[x][y] ? tempDist[x][y] : -1;
        }

        return Arrays.stream(dist[start]).allMatch(v -> v != -1);
    }

    public static int tsp() {
        for (int mask = 1; mask < (1 << dustCount); mask++) {
            for (int i = 0; i < dustCount; i++) {
                if ((mask & (1 << i)) == 0 || dp[mask][i] == Integer.MAX_VALUE) continue;

                for (int j = 0; j < dustCount; j++) {
                    if (i == j || (mask & (1 << j)) != 0 || dist[i][j] == -1) continue;
                    int nextMask = mask | (1 << j);
                    dp[nextMask][j] = Math.min(dp[nextMask][j], dp[mask][i] + dist[i][j]);
                }
            }
        }

        return Arrays.stream(dp[(1 << dustCount) - 1]).min().orElse(-1);
    }
}

---

⏱️ 시간 복잡도 분석

📌 O(W × H + N² + 2ᴺ × N) (최대 10개의 먼지 처리 가능)
💡 bfs() → O(W × H) (각 지점 간 최단 거리 탐색)
💡 dp → O(2ᴺ × N²) (비트마스킹 + DP)
🔥 먼지가 10개 이하이므로 비트마스킹 + DP 방식으로 해결 가능

---

💡 느낀점

✅ BFS로 거리 계산 + 비트마스킹 DP로 최적 경로 찾기가 핵심
✅ TSP(외판원 문제) 응용 문제로 비트마스킹 DP 사용법 익힐 수 있었다
✅ 먼지 간 이동 불가능한 경우를 미리 확인하여 -1 출력하도록 개선
✅ 비트마스크(1 << i)를 활용한 DP 문제 해결 능력 향상! 🚀