[백준 4991] 로봇청소기 -JAVA // le_effort//

까다로운 문제였다.

 

사용하는 알고리즘 = bfs , dfs를 이용한 순열

 

방문했던 칸을 계속 방문 할 수 있다는 것은 일반적인 bfs를 하는게 아니라

전체 거리를 구해줘야함 

전체거리란 2번 설명에 있음

 

전체적인 흐름은

1. 방문할 수 없는 더러운 칸이 존재하는가?  존재하면 -1 출력하고 끝

 

public static boolean isPossible(int x, int y) {
        int copy_map [][] = new int[h][w];
        for(int i=0; i<h; i++) {
            for(int j=0; j<w; j++) {
                copy_map[i][j] = map[i][j];
            }
        }
        boolean[][] visited = new boolean[h][w];
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(x,y));
        
        while(!q.isEmpty()) {
            Node a = q.poll();
            for(int i=0; i<4; i++) {
                int nx = a.x+dx[i];
                int ny = a.y+dy[i];
                if(nx>=0 && ny>=0 && nx<h && ny<w) {
                    if(!visited[nx][ny] && copy_map[nx][ny]!='x') {
                        visited[nx][ny] = true;
                        copy_map[nx][ny]='.';
                        q.add(new Node(nx,ny));
                    }
                }
            }
        }
        for(int i=0; i<h; i++) {
            for(int j=0; j<w; j++) {
                if(copy_map[i][j]=='*') {
                    return false;
                }
            }
        }
        return true;
    }

이 경우는 copy_map 을 만들어 방문할 수 있는 곳 (가구를 제외하고)

전부다.으로 바꿔주고

bfs가 끝나고 먼지가 남아있으면 false

 

 

2. 예를 들어 로봇청소기 1대 먼지가 3개면 모든 경로를 구해줌

로봇 ->먼지1 

로봇 -> 먼지2

로봇 -> 먼지 3

 

먼지 1-> 로봇

먼지 1-> 먼지 2

먼지 1-> 먼지 3

 

먼지 2-> 로봇

먼지 2-> 먼지 1

먼지 2-> 먼지 3

 

아래 코드에서 list 에 들어있는 것은

로봇청소기와 먼지들이다.

dist = new int[dust+1][dust+1];    // dist[1][3] = 1번 먼지에서 3번먼지로 가는데 걸리는 경로 
                                                        // 즉 dist[i][j] = i번 먼지에서 j번 먼지까지 가는데 걸리는 경로
                                                        // 크기가 dust+1인 이유는 로봇청소기도 포함시켜야함으로 먼지수 + 로봇청소기1대
            
            for(int i=0; i<list.size(); i++) {
                int temp[][] = bfs(list.get(i));
                for(int j=i+1; j<list.size(); j++) {
                    dist[i][j] = temp[list.get(j).x][list.get(j).y];
                    dist[j][i] = temp[list.get(j).x][list.get(j).y];
                }
            }

 

public static int[][] bfs(Node o) {
        int[][] temp = new int[h][w];
        boolean visited[][] = new boolean[h][w];
        Queue<Node>q = new LinkedList<>();
        q.add(o);
        while(!q.isEmpty()) {
            Node a = q.poll();
            for(int i=0; i<4; i++) {
                int nx = a.x+dx[i];
                int ny = a.y+dy[i];
                if(nx>=0 && ny>=0 && nx<h && ny<w) {
                    if(!visited[nx][ny]&& map[nx][ny]!='x') {
                        visited[nx][ny] = true;
                        q.add(new Node(nx,ny));
                        temp[nx][ny] = temp[a.x][a.y]+1;
                    }
                }
            }
        }
        return temp ;
    }

3. 순열로 로봇과 먼지의 순서를 뽑아줌 (주의해야 할 건 항상 로봇이 처음에 있어야 함)

public static void dfs(int level) {
        if(level == list.size()) {
            int sum =0;
            int left=0;
            int right=1;
            while(right!=level) {
                sum+=dist[tmp[left]][tmp[right]];
                left++;
                right++;
            }
            min = Math.min(min, sum);
            return ;
        }
        for(int i=1; i<list.size(); i++) {
            if(!dfs_visited[i]) {
                dfs_visited[i] = true;
                tmp[level]=i;
                dfs(level+1);
                dfs_visited[i] = false;
            }
        }
    }

left와 right를 둔 이유는

순열이 0 1 2 3 (0은 로봇청소기)

나왔을 때

0->1 경로 + 1->2 경로 + 2->3 경로를 해주기 위해 설정해둠

 

전체 코드

 

import java.io.*;
import java.util.*;
public class Main {
    static int w,h;
    static Character map [][];
    static int dust=0;
    static boolean dfs_visited[];
    static int tmp[];
    static int dist[][];
    static int start_x, start_y;
    static int min =Integer.MAX_VALUE;
    static int dx[] = {0,0,1,-1};
    static int dy[] = {1,-1,0,0};
    static ArrayList<Node> list = new ArrayList<>();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
            min =  Integer.MAX_VALUE;
            dust=0;
            list.clear();
            String[] t = br.readLine().split(" ");
            w = Integer.parseInt(t[0]);
            h = Integer.parseInt(t[1]);
            if(w==0 && h==0) {
                break;
            }
            map = new Character[h][w];
 
            
            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') {
                        start_x=i;
                        start_y=j;
                        list.add(new Node(i,j));
                    }
                }
            }
            
            for(int i=0; i<h; i++) {
                for(int j=0; j<w; j++) {
                    if(map[i][j]=='*') {
                        dust++;
                        list.add(new Node(i,j));
                    }
                }
            }
            if(!isPossible(start_x,start_y)) {
                System.out.println(-1);
            }
            else {
            dist = new int[dust+1][dust+1];    // dist[1][3] = 1번 먼지에서 3번먼지로 가는데 걸리는 경로 
                                                        // 즉 dist[i][j] = i번 먼지에서 j번 먼지까지 가는데 걸리는 경로
                                                        // 크기가 dust+1인 이유는 로봇청소기도 포함시켜야함으로 먼지수 + 로봇청소기1대
            
            for(int i=0; i<list.size(); i++) {
                int temp[][] = bfs(list.get(i));
                for(int j=i+1; j<list.size(); j++) {
                    dist[i][j] = temp[list.get(j).x][list.get(j).y];
                    dist[j][i] = temp[list.get(j).x][list.get(j).y];
                }
            }
            tmp = new int[dust+1];
            tmp[0]=0;
            dfs_visited = new boolean[dust+1];
            dfs_visited[0] = true;
            dfs(1);
            System.out.println(min);
            }
        }
        
    }
    public static boolean isPossible(int x, int y) {
        int copy_map [][] = new int[h][w];
        for(int i=0; i<h; i++) {
            for(int j=0; j<w; j++) {
                copy_map[i][j] = map[i][j];
            }
        }
        boolean[][] visited = new boolean[h][w];
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(x,y));
        
        while(!q.isEmpty()) {
            Node a = q.poll();
            for(int i=0; i<4; i++) {
                int nx = a.x+dx[i];
                int ny = a.y+dy[i];
                if(nx>=0 && ny>=0 && nx<h && ny<w) {
                    if(!visited[nx][ny] && copy_map[nx][ny]!='x') {
                        visited[nx][ny] = true;
                        copy_map[nx][ny]='.';
                        q.add(new Node(nx,ny));
                    }
                }
            }
        }
        for(int i=0; i<h; i++) {
            for(int j=0; j<w; j++) {
                if(copy_map[i][j]=='*') {
                    return false;
                }
            }
        }
        return true;
    }
    public static void dfs(int level) {
        if(level == list.size()) {
            int sum =0;
            int left=0;
            int right=1;
            while(right!=level) {
                sum+=dist[tmp[left]][tmp[right]];
                left++;
                right++;
            }
            min = Math.min(min, sum);
            return ;
        }
        for(int i=1; i<list.size(); i++) {
            if(!dfs_visited[i]) {
                dfs_visited[i] = true;
                tmp[level]=i;
                dfs(level+1);
                dfs_visited[i] = false;
            }
        }
    }
    public static int[][] bfs(Node o) {
        int[][] temp = new int[h][w];
        boolean visited[][] = new boolean[h][w];
        Queue<Node>q = new LinkedList<>();
        q.add(o);
        while(!q.isEmpty()) {
            Node a = q.poll();
            for(int i=0; i<4; i++) {
                int nx = a.x+dx[i];
                int ny = a.y+dy[i];
                if(nx>=0 && ny>=0 && nx<h && ny<w) {
                    if(!visited[nx][ny]&& map[nx][ny]!='x') {
                        visited[nx][ny] = true;
                        q.add(new Node(nx,ny));
                        temp[nx][ny] = temp[a.x][a.y]+1;
                    }
                }
            }
        }
        return temp ;
    }
}
class Node{
    int x,y;
    Node(int x ,int y){
        this.x=x;
        this.y=y;
    }
}