알고리즘/백준 문제 풀이
[BOJ] 4991. 로봇 청소기
바켱서
2020. 8. 6. 16:42
https://www.acmicpc.net/problem/4991
접근 방법
어려웠었다..
처음에는 그냥 BFS만 사용을 해서 차근차근 가까운 순서대로 먼지를 먹어주면 되는 줄 알았다.
하지만 구현은 완벽했지만 틀리는 것을 보고 아래의 힌트를 보았더니
' 순열 ' 이 포함 되어 있는 것을 보고
이 문제의 핵심은 청소기가 먼지를 먹는 순서에 따라 결과 값이 달라진다는 것을 알았다.
푸는 방식은 이렇게 했다.
입력 값을 받을 때 모든 먼지들의 값을 배열에 따로 저장을 한다.
각각의 먼지들의 거리를 BFS로 구한다.
/** * 각각의 먼지를 구한 값 * dust_dist[0][1] -> 이 뜻은 먼지들의 배열에서 0 에서 1로 갈 때의 distance의 값이다. **/ static void getDustDist(){ for(int i=0; i<total_dust.size()-1; i++){ for(int k=i+1; k<total_dust.size(); k++){ temp_dust_dist = Integer.MAX_VALUE; visit = new int[h][w]; queue = new LinkedList<>(); visit[total_dust.get(i).x][total_dust.get(i).y] = 1; queue.add(total_dust.get(i)); // getPartialDist == BFS(endLocation) getPartialDist(total_dust.get(k)); dust_dist[i][k] = temp_dust_dist; dust_dist[k][i] = temp_dust_dist; } } }청소기에서 각각의 먼지들의 거리 또한 존재해야 하기 때문에 구하고 배열에 넣는다.
static void getCleanerDustDist(){ for(int i=0; i<total_dust.size(); i++){ temp_dust_dist = Integer.MAX_VALUE; visit = new int[h][w]; queue = new LinkedList<>(); visit[cleaner.x][cleaner.y] = 1; queue.add(cleaner); getPartialDist(total_dust.get(i)); cleaner_dust_dist[i] = temp_dust_dist; } }이제 어느 먼지를 먼저 먹을 지에 대한 순열을 구하고 ans에 최소값을 대입해주면 된다.
static void permutation(int[] arr, int depth, int r) { if (depth == r) { ans = Math.min(ans,getTotalDist(arr)); return; } for (int i=depth; i<total_dust.size(); i++) { swap(arr, depth, i); permutation(arr, depth + 1, r); swap(arr, depth, i); } } static int getTotalDist(int[] arr) { int tempTotalDist = 0; tempTotalDist = cleaner_dust_dist[arr[0]]; if(tempTotalDist == Integer.MAX_VALUE) return Integer.MAX_VALUE; for(int i=0; i<arr.length-1; i++){ int dist = dust_dist[arr[i]][arr[i+1]]; if(dist == Integer.MAX_VALUE) return Integer.MAX_VALUE; tempTotalDist += dist; } return tempTotalDist; }
Need Know
- BFS
- 순열
전체 코드 ( Java )
import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int w;
static int h;
static char[][] map;
static int[][] dust_dist;
static int[] cleaner_dust_dist;
static Queue<Location> queue;
static int temp_dust_dist;
static int[][] visit;
static ArrayList<Location> total_dust;
static Location cleaner;
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
static int ans ;
public static void main(String[] args) throws IOException {
set();
bw.flush();
bw.close();
br.close();
}
static void set() throws IOException {
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];
ans = Integer.MAX_VALUE;
total_dust = new ArrayList<>();
for(int i=0; i<h; i++){
String str = br.readLine();
for(int k=0; k<w; k++){
map[i][k] = str.charAt(k);
if(map[i][k]=='o') cleaner = new Location(i,k);
if(map[i][k]=='*') total_dust.add(new Location(i,k));
}
}
cleaner_dust_dist = new int[total_dust.size()];
dust_dist = new int[total_dust.size()][total_dust.size()];
getCleanerDustDist();
getDustDist();
int[] index_arr = new int[total_dust.size()];
for(int i = 0; i<total_dust.size(); i++){
index_arr[i] = i;
}
permutation(index_arr, 0, total_dust.size());
if(ans == Integer.MAX_VALUE) bw.write(-1 + "\n");
else{
bw.write(ans +"\n");
}
}
}
static void permutation(int[] arr, int depth, int r) {
if (depth == r) {
ans = Math.min(ans,getTotalDist(arr));
return;
}
for (int i=depth; i<total_dust.size(); i++) {
swap(arr, depth, i);
permutation(arr, depth + 1, r);
swap(arr, depth, i);
}
}
static int getTotalDist(int[] arr) {
int tempTotalDist = 0;
tempTotalDist = cleaner_dust_dist[arr[0]];
if(tempTotalDist == Integer.MAX_VALUE) return Integer.MAX_VALUE;
for(int i=0; i<arr.length-1; i++){
int dist = dust_dist[arr[i]][arr[i+1]];
if(dist == Integer.MAX_VALUE) return Integer.MAX_VALUE;
tempTotalDist += dist;
}
return tempTotalDist;
}
static void swap(int[] arr, int depth, int i) {
int temp = arr[depth];
arr[depth] = arr[i];
arr[i] = temp;
}
static void getCleanerDustDist(){
for(int i=0; i<total_dust.size(); i++){
temp_dust_dist = Integer.MAX_VALUE;
visit = new int[h][w];
queue = new LinkedList<>();
visit[cleaner.x][cleaner.y] = 1;
queue.add(cleaner);
getPartialDist(total_dust.get(i));
cleaner_dust_dist[i] = temp_dust_dist;
}
}
static void getDustDist(){
for(int i=0; i<total_dust.size()-1; i++){
for(int k=i+1; k<total_dust.size(); k++){
temp_dust_dist = Integer.MAX_VALUE;
visit = new int[h][w];
queue = new LinkedList<>();
visit[total_dust.get(i).x][total_dust.get(i).y] = 1;
queue.add(total_dust.get(i));
getPartialDist(total_dust.get(k));
dust_dist[i][k] = temp_dust_dist;
dust_dist[k][i] = temp_dust_dist;
}
}
}
static void getPartialDist(Location end){
loop : while(!queue.isEmpty()){
Location nowLoc = queue.poll();
for(int i=0; i<4; i++){
int nx = nowLoc.x + dx[i], ny = nowLoc.y + dy[i];
if(nx >= h || ny >= w || nx < 0 || ny < 0 || visit[nx][ny] != 0 || map[nx][ny] == 'x') continue;
if( nx == end.x && ny == end.y ){
temp_dust_dist = visit[nowLoc.x][nowLoc.y];
break loop;
}
queue.add(new Location(nx,ny));
visit[nx][ny] = visit[nowLoc.x][nowLoc.y] +1;
}
}
}
}class Location{
int x;
int y;
public Location(int x, int y) {
this.x = x;
this.y = y;
}
}