BOJ G1 4991 로봇 청소기 JAVA

4991번: 로봇 청소기

---

문제 읽기

일단 처음 읽었을 때는 비트마스킹을 쓰는 문제인가? 싶었다. 맵의 크기가 20x20으로 작긴 하지만, 같은 칸을 여러 번 방문할 수 있다는 조건이 있었기 때문에, 큐에 visited를 계속 넣으면 잘못하면 메모리초과가 날 수도 있다고 생각했다. 그런데 비트마스킹을 어떻게 하는지 잘 생각이 안 나서 일단 다른 방법을 또 생각했다.

 

두 번째로 생각한 건, 더러운 곳을 각각 하나의 노드로 보고, 로봇 청소기(시작 위치)와 더러운 곳 사이의 거리, 그리고 노드간 거리를 다 구해두고, 순열로 더러운 곳을 방문할 순서를 완탐으로 구해서 최소 거리를 계산하는 방식이다.

이 방식으로 문제를 해결했다.

---

문제 풀기

크게 생각할 문제는 없다. 단순히 다음 과정을 따라서 문제를 해결하면 된다.

1. 입력 받을 때 로봇 청소기의 위치(시작 위치)와 더러운 곳의 위치를 저장한다.
2. BFS를 이용해 미리 최소 거리를 구한다.
   1. 로봇 청소기~더러운 곳 의 최소 거리를 startDist[] 배열에 저장한다.
   2. 더러운 곳~다른 더러운 곳의 최소 거리를 dist[][] 배열에 저장한다.
3. 더러운 곳을 permutation하여 줄 세운다
   1. 줄을 다 세우면 그때마다 미리 구한 거리 값을 이용해 총 최소 거리를 계산하고 갱신한다.
4. 최종 최소 거리를 출력한다.

---

실수한 부분

근데 실수한 부분이 있다. 제출했더니 계속 10퍼센트에서 틀렸다.

질문 게시판 반례도 다 넣어보고, 글도 다 읽어봤는데 나에게 해당되는 내용이 없었다. 그리고 코드도 다시 찬찬히 뜯어보면서 초기화가 안된 게 있는지 확인했는데 그런 것도 없었다.

 

그래서 질문 게시판에서 엄청 많은 테케가 있는 글이 있었는데, 이걸 넣어보고 깨달았다.

글 읽기 - 테케 공유

너무 많아서 그냥 일단 다 넣어봤는데, 저렇게 튀는 값이 있었다.

알고 보니 dist 배열의 초기값이 너무 커서 더하는 과정에서 오버플로우가 생긴 것..

그래서 이 부분을 고쳐줬더니 해결됐다.

 

<고치는 법>

• INF 크기 줄인다
• 더하는 과정에서 INF면 그냥 그 값은 버린다.

---

코드

package ps.GraphSearch;

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

public class BOJ_G1_4991_로봇청소기 {
    /*
    구상
    1. 더러운 칸 하나를 하나의 노드로 보고, 모든 더러운 칸들 사이의 거리를 구한다.
        1.1 여기서 아무 노드도 갈 수 없는 곳이 있으면(거리가 다 무한대) -1을 출력하고 끝낸다.
    2. 순열을 사용해서 더러운 칸들을 줄세운다.
        2.1 줄 다 세우면 그 순서대로 이동하는 데에 걸리는 비용을 계산하여, 최소를 저장한다
     */
    static class Pos{
        int r, c;
        int depth;
        public Pos(int r, int c){
            this.r = r;
            this.c = c;
        }
        public Pos(int r, int c, int depth){
            this.r = r;
            this.c = c;
            this.depth = depth;
        }
    }
    static int H, W;
    static char[][] map;
    static int[][] intMap;
    static Pos start;
    static List<Pos> dirty; //노드들 저장
    static int[] startDist; //시작점에서 노드들까지의 거리 저장
    static int[][] dist; //더러운 노드들 사이의 거리 저장
    static int INF = Integer.MAX_VALUE / 21;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        StringBuilder sb = new StringBuilder();
        while(true){
            StringTokenizer st = new StringTokenizer(in.readLine());
            W = Integer.parseInt(st.nextToken());
            H = Integer.parseInt(st.nextToken());
            if (H == 0 && W == 0) break;

            map = new char[H][W];
            intMap = new int[H][W];
            dirty = new ArrayList<>();
            int idx = 0;
            for (int i = 0; i < H; i++){
                map[i] = in.readLine().toCharArray();
                Arrays.fill(intMap[i], -1);
                for (int j = 0; j < W; j++){
                    if (map[i][j] == 'o') start = new Pos(i, j);
                    else if (map[i][j] == '*') {
                        dirty.add(new Pos(i, j));
                        intMap[i][j] = idx++;
                    }
                }
            }

            //거리 구하기
            //dist 초기화
            startDist = new int[dirty.size()];
            dist = new int[dirty.size()][dirty.size()];
            Arrays.fill(startDist, INF);
            getDist(start, startDist); //start부터 다른 곳까지의 거리
            for (int i = 0; i < dirty.size(); i++){
                Arrays.fill(dist[i], INF);
                dist[i][i] = 0;

                Pos pos = dirty.get(i);
                getDist(pos, dist[i]);
            }

//            System.out.println(Arrays.toString(startDist));

            //순열로 줄세우기
            numbers = new int[dirty.size()];
            used = new boolean[dirty.size()];
            minCost = Integer.MAX_VALUE;
            permutation(dirty.size(), 0); //총 숫자, cnt
            sb.append((minCost >= INF)? -1 : minCost).append("\\n");
        }
        System.out.println(sb);
    }

    static int[] numbers;
    static boolean[] used;
    private static void permutation(int size, int cnt) {
        if (cnt == size){
            calculateCost();
            return;
        }
        for (int i = 0; i < size; i++){
            if (used[i]) continue;

            used[i] = true;
            numbers[cnt] = i;
            permutation(size, cnt+1);
            used[i] = false;
        }
    }

    static int minCost;
    private static void calculateCost() {
        int cost = startDist[numbers[0]];
        for (int i = 0; i < numbers.length-1; i++){
            cost += dist[numbers[i]][numbers[i+1]];
        }
        minCost = Math.min(minCost, cost);
    }

    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    private static void getDist(Pos start, int[] dist) {
        //bfs를 수행하여 구하기
        Queue<Pos> q = new ArrayDeque<>();
        boolean[][] visited = new boolean[H][W];

        q.offer(start);
        visited[start.r][start.c] = true;

        while(!q.isEmpty()){
            Pos cur = q.poll();

            for (int di = 0; di < 4; di++){
                int nr = cur.r + dr[di];
                int nc = cur.c + dc[di];
                if (nr < 0 || nr >= H || nc < 0 || nc >= W || visited[nr][nc] || map[nr][nc] == 'x') continue;

                visited[nr][nc] = true;
                if (intMap[nr][nc] != -1){
                    //더러운 곳임
                    dist[intMap[nr][nc]] = cur.depth + 1;
                }
                q.offer(new Pos(nr, nc, cur.depth+1));
            }
        }
    }
}