[JAVA] 4991 로봇청소기

안녕하세요. 오늘 풀어 볼 문제는 로봇청소기 입니다. 

 

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

4991번: 로봇 청소기

 

친구에게 선물로 로봇청소기를 준적이 있는데, 그때 생각이 나는군요. 가격이 비싸서 눈물이 나왔답니다. 

 

오랜만에 글을 쓰다보니 첫 잡담부터 아주 정성스럽게 쓰고 있습니다. 문제 풀이보다 더 고심해서 쓰는 듯..

 

아무튼 풀어 보겠습니다.

 

 

<나의 풀이> 

 

처음에는 단순하게 접근을 해서 코드를 구현했습니다. 

 

청소기부터 시작 > 쓰레기를 만날때 까지 BFS를 수행 > 쓰레기를 만나면 다시 BFS를 수행

 

물론 틀렸습니다.

 

그 예로.

x...*O*...*x

x*..*O*....x

 

이런 상황에서는 최단쓰레기로만 이동한다면 최솟값을 구할 수 없습니다. 정확하게 말하면 못 구하는 경우도 있습니다.

> 그리디하게 구하는 것이 안된다

 

 

그래서 다른 방법을 생각해보았습니다. 

 

문제를 읽다보면 쓰레기의 갯수가 10를 넘지않는다는 조건이 있습니다. 게다가 가로와 세로 또한 20 이하입니다.

 

늘 최솟값을 구하는 문제는 결국 모든 값을 확인을 해야합니다. 위의 조건을 보니 충분히 가능한 범위인것 같습니다.

 

그럼 어떤 방식으로 모든 경우를 확인하는지가 핵심인것 같습니다. 

 

1. 쁘루트 포스 

어차피 모든 경로를 봐야하니 진짜 모든 경우를 다 확인하는 방법입니다.

쓰레기가 최대 9개인경우 9! (대략 30만)

9! x n^2 (n은 최대 20) > (대략 1200만)

9! x n^2 (n은 최대 20) x 주어지지 않은 테스트 케이스의 수..

보통 1억번이 1초라고 생각하니 1초를 넘을 가능성이  아주 큽니다.

 

2. 프림알고리즘(과 비슷) 혹은 순열..?

각 쓰레기들의 거리를 계산후, 최단 거리를 구합니다. 

쓰레기와 청소기를 합한 10 개중 2개를 선택하는 경우 > 10C2 (45)

45 x n^2(BFS 시간 복잡도) + 10^3(프림 알고리즘 시간복잡도) 

충분히 가능보입니다.

 

2번을 선택하여 코드를 구현했습니다.

 

<코드>

import java.io.*;
import java.util.*;
class Point{
    int h;
    int w;
    int dist;
    public Point (int h, int w,int dist){
        this.h = h;
        this.w = w;
        this.dist = dist;
    }
}
public class Num4991 {
    static char[][] map;
    static List<Point> startingpoint;
    static int[][] distInfo;
    static boolean[] vist;
    static int answer = Integer.MAX_VALUE;
    static int[] dx ={1,0,-1,0} , dy ={0,1,0,-1};
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        while(true){
            String[] input = bf.readLine().split(" ");
            int w = Integer.parseInt(input[0]);
            int h = Integer.parseInt(input[1]);
            if(w==0 || h == 0){
                break;
            }
            map = new char[h][w];
            startingpoint = new ArrayList<>();
            for(int i=0;i<h;i++){
                String mapinput = bf.readLine();
                for(int j=0; j<w; j++){
                    map[i][j] = mapinput.charAt(j);
                    if(mapinput.charAt(j)=='o'){
                        startingpoint.add(0,new Point(i,j,0));
                    }else if(mapinput.charAt(j)=='*'){
                        startingpoint.add(new Point(i,j,0));
                    }
                }
            }
            answer =Integer.MAX_VALUE;
            solution(h,w);
            sb.append(answer+"\n");
        }
        System.out.print(sb);
    }
    public static void solution(int h, int w){
        int startPointNum = startingpoint.size();
        distInfo = new int[startPointNum][startPointNum];
        for(int i=0;i<startPointNum-1;i++){
            for(int j=i+1;j<startPointNum;j++){
                if(i==j){distInfo[i][j]=0;}
                //시작점과 끝 점을 기준으로 구했습니다.
                distInfo[i][j] = bfs(h,w,startingpoint.get(i),startingpoint.get(j));
                distInfo[j][i] = distInfo[i][j];
                if(distInfo[i][j]==-1){
                    answer=-1;
                    return;
                }
            }
        }
        vist = new boolean[startPointNum];
        vist[0] = true;
        dfs(0,1,0,startPointNum);
    }
    public static int bfs(int h, int w, Point start, Point end){
        boolean[][] vist = new boolean[h][w];
        Queue<Point> bfsque = new LinkedList<>();
        bfsque.add(start);
        vist[start.h][start.w] = true;
        while(!bfsque.isEmpty()){
            Point going = bfsque.poll();
            if(going.h==end.h && going.w == end.w){
                return going.dist;
            }
            for(int i=0;i<4;i++){
                if(going.h+dx[i]>=0 && going.h+dx[i]<h && going.w+dy[i]>=0 && going.w+dy[i]<w){
                    if(vist[going.h+dx[i]][going.w+dy[i]]){
                        continue;
                    }
                    if((map[going.h+dx[i]][going.w+dy[i]]=='x')) {
                        continue;
                    }
                    bfsque.add(new Point(going.h+dx[i],going.w+dy[i], going.dist+1));
                    vist[going.h+dx[i]][going.w+dy[i]] = true;
                }
            }
        }
        return -1;
    }
    public static void dfs(int start, int sum, int cost,int startpointnum){
        if(sum == startpointnum){
            answer =Math.min(cost,answer);
            return;
        }
        for(int i=1;i<vist.length;i++){
            if(!vist[i]){
                vist[i] = true;
                dfs(i,sum+1,distInfo[start][i]+cost,startpointnum);
                vist[i] = false;
            }
        }
    }
}

 

<후기>

이상한 곳에서 잘못해서 하루종일 삽질했다. 매우 화가났다

쓰레기간의 거리를 10번의(각 쓰레기를 기준으로) BFS로 구하기도 가능하다.

Stream을 쓰는 것을 연습하자.

 

아 japan 2005 ICPC문제 테스트 케이스 모여있는 곳입니다.

 

https://icpc.iisf.or.jp/past-icpc/domestic2005/

ICPC2005 Problems(Domestic)

저는 메모리 초과를 테스트케이스 넣어보고 찾았습니다..(잘못된 좌표의 vist[ ][ ] 설정으로 인한 큐 메모리 초과)