BOJ_4991_로봇 청소기 (Java)

[Gold I] 로봇 청소기 - 4991

문제 링크

성능 요약

메모리: 118492 KB, 시간: 540 ms

분류

그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 비트마스킹

제출 일자

2025년 5월 26일 11:03:27

문제 설명

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

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

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

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

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

입력

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

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

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

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

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

출력

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

문제 풀이

핵심 아이디어 : 로봇이 어떤 더러운 칸들을 청소했는지를 비트마스크로 상태를 관리하는 것 더러운 칸이 최대 10개이므로 2^10 = 1024가지 상태를 표현할 수 있다.

1. 로봇의 시작 위치를 찾고, 모든 더러운 칸의 좌표를 저장.
2. BFS로 탐색하면서 각 칸에 대해 (r, c, state) 형태로 방문 체크. 여기서 state는 어떤 더러운 칸들을 청소했는지를 나타내는 비트마스크
3. 더러운 칸에 도달하면 해당 비트를 켜서 새로운 상태를 만들고, 모든 더러운 칸을 청소했는지 확인.
4. 모든 더러운 칸을 청소한 상태가 되면 그때의 이동 횟수가 최솟값.

• 시간복잡도: $O(N × M × 2^{10})$ 이며, 각 칸마다 가능한 모든 청소 상태를 고려하여 탐색

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {

    class Cell{
        int r, c, state, dist;
        public Cell(int r, int c, int state, int dist) {
            this.r = r;
            this.c = c;
            this.state = state;
            this.dist = dist;
        }
    }

    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static int N, M;
    static int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1};
    static char[][] board;
    static List<int[]> dirty; // 입력순서대로 더러운칸 번호
    static Map<Integer, Integer> dirtyMap; // 더러운 곳 (r, c) 로 해싱해서 몇번째 더러운 칸인지 체크
    static boolean[][][] visited;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_4991_로봇청소기/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        while(true) {
            st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());

            if(N == 0 && M == 0) break;
            board = new char[N][M];
            dirty = new ArrayList<>();
            dirtyMap = new HashMap<>();
            Cell start = new Cell(0,0,0,0);
            int num = 0;
            for(int i = 0; i < N; i++) {
                String Line = br.readLine();
                for(int j = 0; j < M; j++) {
                    board[i][j] = Line.charAt(j);
                    if(board[i][j] == '*') {
                        dirty.add(new int[]{i, j});
                        dirtyMap.put(j + i*M, num++);
                    }
                    else if(board[i][j] == 'o'){
                        start.r = i;
                        start.c = j;
                    }
                }
            }

            Queue<Cell> queue = new ArrayDeque<>();
            visited = new boolean[N][M][1<<10];
            queue.add(start);
            visited[start.r][start.c][0] = true;

            boolean flag = false;
            while(!queue.isEmpty() && !flag) {
                Cell curr = queue.poll();
                for(int k=0; k<4; k++) {
                    int nr = curr.r + dr[k];
                    int nc = curr.c + dc[k];
                    if(isValid(nr, nc) && board[nr][nc] != 'x') {
                        if(board[nr][nc] == '*'){
                            int n = dirtyMap.get(nc + nr*M); // 몇번째 더러운 칸인지
                            int nstate = curr.state | (1 << n); // 새로운 state값

                            if(nstate == ((1<<dirty.size()) - 1)) {
                                sb.append(curr.dist + 1).append("\n");
                                flag = true;
                                break;
                            }
                            Cell nextCell = new Cell(nr, nc, nstate, curr.dist + 1);
                            if(!visited[nr][nc][nstate]){
                                visited[nr][nc][nstate] = true;
                                queue.add(nextCell);
                            }
                        }
                        else if(board[nr][nc] == '.' || board[nr][nc] == 'o') {
                            Cell nextCell = new Cell(nr, nc, curr.state, curr.dist + 1);
                            if(!visited[nr][nc][curr.state]){
                                visited[nr][nc][curr.state] = true;
                                queue.add(nextCell);
                            }
                        }
                        else continue;
                    }
                }
            }

            if(!flag){
                sb.append("-1\n");
            }
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    private boolean isValid(int r, int c){
        return r >= 0 && r < N && c >= 0 && c < M;
    }
}