[백준] 4991 로봇 청소기

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

4991번: 로봇 청소기

2021-10-11

---

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 Main {
    public static int N, M, answer, len;
    public static char[][] arr;
    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, -1, 0, 1};
    public static Queue<Clean> q;
    public static boolean[][][] vtd;
    public static boolean flag;
    public static class Clean {
        int x;
        int y;
        int key;
 
        public Clean(int x, int y, int key) {
            this.x = x;
            this.y = y;
            this.key = key;
        }
    }
    public static void solve() {
        answer = 0;
        loop:while(!q.isEmpty()) {
            int size = q.size();
            while(size > 0) {
                Clean tmp = q.poll();
                int x = tmp.x;
                int y = tmp.y;
                int key = tmp.key;
                if(key == (1 << len) - 1) {
                    flag = true;
                    break loop;
                }
 
                for(int i = 0; i < dx.length; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    if(nx < 0 || ny < 0 || nx >= N || ny >= M || arr[nx][ny] == 'x' || vtd[nx][ny][key]) continue;
                    else {
                        int tmpKey = key;
                        if(arr[nx][ny] >= 'a' && arr[nx][ny] <= 'k') {
                            tmpKey = key | 1 << arr[nx][ny] - 'a';
                        }
                        q.add(new Clean(nx, ny, tmpKey));
                        vtd[nx][ny][tmpKey] = true;
                    }
                }
                size--;
            }
            answer++;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        while(true) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            if(M == 0 && N == 0)break;
            arr = new char[N][M];
            q = new LinkedList<>();
            len = 97;
            flag = false;
            for(int i = 0; i < N; i++) {
                st = new StringTokenizer(bf.readLine());
                String str = st.nextToken();
                for(int j = 0; j < M; j++) {
                    arr[i][j] = str.charAt(j);
                    if(arr[i][j] == 'o') {
                        q.add(new Clean(i, j, 0));
                    } else if(arr[i][j] == '*') {
                        arr[i][j] = (char) len;
                        len++;
                    }
                }
            }
            len-=97;
            vtd = new boolean[N][M][1<<len];
            solve();
            if(flag) sb.append(answer).append("\n");
            else sb.append("-1").append("\n");
        }
        System.out.println(sb.toString());
    }
}
 

#문제풀이

BFS + 비트마스킹

1. 더러운 곳을 'a' ..부터 순서대로 표시했다. ('A'로 해도 된다 65부터..)

2. 돌아다니면서 key(청소한 곳)값을 저장해놓고, 비트마스킹을 이용해서 이미 청소한 곳인지 아닌지 체크해서 마지막에 모두 청소했으면 함수를 끝냈다. 

 

풀고 나서 다른 사람들 풀이를 보니 청소기와 먼지, 먼지와 먼지 사이의 거리들의 모든 거리를 구한 후 순열을 이용해서 모든 순서를 구해서 최소거리를 찾는 방식으로 많이 푼 것을 확인했다.