[JAVA] 백준 4991 : 로봇 청소기

문제

4991번: 로봇 청소기

 

해결 방법

처음엔 우선순위큐를 활용한 BFS로 거리를 계산해서 최소 거리를 알아내면 될 것 같아서 시도해보았는데, 

최소 거리로 움직이면서 다음으로 탐색하는게 전체적으로 더러운 칸을 모두 제거하였을 때 최소 거리가 아닐 수도 있다고 한다.

그래서 처음에 짠 코드는 실패하였다.

 

해결한 방법은 다음과 같다.

먼저 로봇과 각 더러운 칸들 간의 거리를 정리할 배열을 생성해두고 값을 넣어주어야한다.

BFS 탐색을 활용해서 로봇에서 더러운 칸의 거리들, 더러운 칸들과 더러운 칸들 사이의 거리를 distance 배열에 넣어주었다.

그리고 순열과 같은 방식으로 로봇 -> 각 더러운 칸들로 향하는 모든 경우의 수를 구해서 가장 최소 거리인 값을 구해준다.

 

로봇과 더러운 칸들은 list에 담아서 사용하였는데, 로봇은 index를 활용해서 무조건 0번째에 입력을 받을 수 있게 하였다.

또 로봇이 방문 불가능한 더러운 칸이 있는지 여부는 처음 입력을 받을 때 로봇과 더러운 칸 전부를 list에 담아두었기 때문에 로봇을 BFS로 탐색할 때 방문한 더러운 칸의 갯수를 dirty를 활용하여 확인 한 뒤에 list의 크기 - 1(로봇을 제외한 값)과 일치하지않으면 방문이 불가능한 더러운 칸이 있는 것으로 간주하고 -1 을 출력하게 하였다.

 

순열과 같이 전체의 경우의 수를 따져가며 최소의 값을 구하는 것을 생각하는게 어려웠던 문제였다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int[] dx = {0, 0, -1, 1};
	static int[] dy = {-1, 1, 0, 0};
	
	static int h, w;
	static char[][] map;
	static boolean[][] visit;
	static int[][] distance;
	static int dirty;
	static ArrayList<Node> list;
	
	static boolean[] check;
	static int result;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        while (true) {
        	StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        	w = Integer.parseInt(st.nextToken());
        	h = Integer.parseInt(st.nextToken());
        	
        	if (w == 0 && h == 0) break;
        	
        	map = new char[h][w];
        	list = new ArrayList<>();
        	
        	for (int i = 0; i < h; i++) {
        		String input = br.readLine();
        		for (int j = 0; j < w; j++) {
        			map[i][j] = input.charAt(j);
        			
        			if (map[i][j] == 'o') {
        				list.add(0, new Node(i, j, 0));
        			} else if (map[i][j] == '*') {
        				list.add(new Node(i, j, 0));
        			}
        		}
        	}
        	distance = new int[list.size()][list.size()];
        	dirty = 0; // 탐색 불가능한 더러운 칸이 있는지 알아보는 용도
        	for (int i = 0; i < list.size(); i++) {
        		bfs(list.get(i), i);
        		// 로봇과 각 더러운 칸들 간의 거리 구하기
        	}
        	
        	if (dirty == list.size() - 1) {
        		// 탐색 불가능한 더러운 칸이 있다면 리스트 크기에서
        		// 로봇을 제외한 크기와 다를 것이다.
        		result = Integer.MAX_VALUE;
            	check = new boolean[list.size()];
            	check[0] = true;
            	find(0, 1, 0);
            	sb.append(result + "\n");
        	} else {
        		sb.append(-1 + "\n");
        	}
        	
        }
        System.out.println(sb);
        
    }
    static void bfs(Node node, int start) {
    	visit = new boolean[h][w];
    	Queue<Node> q = new LinkedList<>();
    	q.offer(node);
    	visit[node.x][node.y] = true;
    	
    	while(!q.isEmpty()) {
    		Node next = q.poll();
    		
    		if (map[next.x][next.y] == '*') {
    			if (start == 0) dirty++;
    			// 로봇에서 시작해서 더러운 칸을 만났을 때만 먼지 갯수 확인
    			
    			for (int i = 1; i < list.size(); i++) {
    				if(next.x == list.get(i).x && next.y == list.get(i).y) {
    					distance[start][i] = next.move;
    				}
        		}
    		}
    		
    		for (int i = 0; i < 4; i++) {
    			int newX = next.x + dx[i];
    			int newY = next.y + dy[i];
    			
    			if (newX < 0 || newY < 0 || newX >= h || newY >= w) continue;
    			if (map[newX][newY] == 'x' || visit[newX][newY]) continue;
    			
    			q.offer(new Node(newX, newY, next.move + 1));
    			visit[newX][newY] = true;
    		}
    	}
    }
    
    static void find(int start, int cnt, int dist) {
    	if (cnt == list.size()) {
    		// 리스트의 모든 칸을 방문하였을 때 이동한 칸수가
    		// 저장된 값보다 작으면 바꾸어줌.
    		result = Math.min(result, dist);
    	}
    	
    	for (int i = 1; i < list.size(); i++) {
    		if (!check[i]) {
    			check[i] = true;
    			find(i, cnt + 1, dist + distance[start][i]);
        		check[i] = false;
    		}
    	}
    }
}

class Node {
	int x;
	int y;
	int move;
	
	Node (int x, int y, int move) {
		this.x = x;
		this.y = y;
		this.move = move;
	}
}