BOJ - 로봇 청소기 4991번 (JAVA)

❓ 문제 - 백준 로봇 청소기 4991번 - JAVA 풀이법

 

출처 

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

4991번: 로봇 청소기

 

 

 

📝 문제해결법

1. 문제 해석

• 로봇 청소기 시작 위치에서 상, 하, 좌, 우 한 칸씩 이동해서 모든 먼지를 청소하는데 필요한 이동 횟소의 최솟값을 구하라
• 가구가 배치된 곳은 방문하지 이동할 수 없으며, 가구때문에 청소할 수 없는 영역이 있다면 -1을 출력한다.

 

2. 해결 방법

• BFS로 지도의 모든 영역 x1, y1 - > x2, y2로 이동하는 최소 이동수를 구한다. 그리고 먼지의 청소 순서를 순열(dfs)를 통해 구해서 각 순서로 먼지를 청소하러 간다고 했을 때 이동 횟수의 총합을 구한 후 이동 횟수의 최솟값으로 갱신한다.
• 우선 w, h가 최대 20이므로 특정 지점에서 다른 지점의 최소 이동 횟수를 모두 구하기 위해 bfs를 돌리면 시간 복잡도 O(20*20*20*20) 으로 연산횟수가 160000 이므로 시간 초과가 발생하지 않는다.
• 우선 BFS로 각 지점에서 특정지점까지 의 최소 이동횟수 모두를 다 구한 뒤, 각 먼지에 방문 순서를 정하는 순열을 구한다.
• 그리고 각 순열의 이동순서에 맞춰 BFS로 구한 최소 이동횟수의 총합을 구한 뒤, 최솟값 갱신을 하는데 만약 중간에 이동할 수 없는 먼지가 있는 경우는 최솟값 갱신을 못하도록 DFS 내에서 return 처리한다.

 

3. 삽질 & 느낀점

• 순열(dfs)에서 특정 지점 -> 다른 지점으로 이동하는 bfs를 계속 구하도록 했지만 시간 초과가 발생하였다. 
• 문제를 자세하게 보면 w, h의 범위도 작고, map은 고정되어 있는 상태에서 특정 지점에서 다른 지점까지의 최소 이동횟수는 항상 같으므로 먼저 BFS로 최소 이동거리들을 구한 뒤 적용하는 것이 시간초과가 나지 않은 방법이었다...
• 다음에 이런 비슷한 유형이 있을 때 먼저 BFS의 모든 지점의 최소 거리를 구하는 로직을 떠올려야지..!

 

💻 소스코드 

// BOJ - 로봇 청소기(4991번)
// DFS + BFS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main_4991_2 {
    public static class Node {
        int x;
        int y;
        int dis;
        public Node(int x, int y){
            this.x = x;
            this.y = y;
        }
        
    }
    public static int n, m, min_dis;
    public static ArrayList<Node> dirty;
    public static int s_x, s_y;
    public static char[][] map;
    public static boolean[] check;
    public static int[][][][] bfs_distance;
    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while (true){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            m = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            if(n == 0 && m == 0) break;
            bfs_distance = new int[n][m][n][m];
            map = new char[n][m];
            dirty = new ArrayList<>();
            for(int i=0;i<n;i++){
                map[i] = br.readLine().toCharArray();
                for(int j=0;j<m;j++){
                    if(map[i][j] == '*'){
                        dirty.add(new Node(i, j));
                    } else if(map[i][j] == 'o'){
                        s_x = i;
                        s_y = j;
                    }
                }
            }
            check = new boolean[dirty.size()];
            min_dis = Integer.MAX_VALUE;
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    bfs(i, j);
                }
            }
            dfs(0, new int[dirty.size()]);
            if(min_dis == Integer.MAX_VALUE) System.out.println(-1);
            else System.out.println(min_dis);

        }


    }

    public static void dfs(int depth, int[] permu){
        if(depth == dirty.size()){
            int dis = 0;
            int r_x = s_x;
            int r_y = s_y;

            for(int i=0;i<permu.length;i++){
                Node d = dirty.get(permu[i]);
                int distance = bfs_distance[r_x][r_y][d.x][d.y];
                if(distance == 0) return;
                dis += distance;
                r_x = d.x;
                r_y = d.y;
            }

            min_dis = Math.min(min_dis, dis);
            return;
        }

        for(int i=0;i<dirty.size();i++){
            if(check[i]) continue;
            check[i] = true;
            permu[depth] = i;
            dfs(depth+1, permu);
            check[i] = false;
        }
    }

    public static void bfs(int x, int y){

        Queue<Node> q = new LinkedList<>();
        q.add(new Node(x, y));
        bfs_distance[x][y][x][y] = 0;
        while (!q.isEmpty()){
            Node node = q.poll();
            for(int i=0;i<4;i++){
                int nx = node.x + dx[i];
                int ny = node.y + dy[i];
                if(nx < 0 || ny < 0 | nx >= n || ny >= m) continue;
                if(map[nx][ny] == 'x') continue;
                if(bfs_distance[x][y][nx][ny] != 0) continue;
                q.add(new Node(nx, ny));
                bfs_distance[x][y][nx][ny] = bfs_distance[x][y][node.x][node.y]+1;
            }
        }
    }
}