[BaekJoon] 4991 로봇 청소기 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    static Reader scanner = new Reader();
    static int w, h, min, massedNum;
    static char[][] map;
    static int[][] distance;
    static Loc[] massedLoc;

    static void input() {
        w = scanner.nextInt();
        h = scanner.nextInt();

        if(w == 0 && h == 0) {
            System.out.print(sb);
            System.exit(0);
        }

        min = Integer.MAX_VALUE; // 각 테스트 케이스의 최소 이동 횟수
        map = new char[h][w];
        massedLoc = new Loc[11]; // 로봇 청소기의 시작 지점 및 더러운 칸의 배열
        massedNum = 1; // 더러운 칸의 개수

        for(int row = 0; row < h; row++) {
            String info = scanner.nextLine();
            for(int col = 0; col < w; col++) {
                map[row][col] = info.charAt(col);

                // 로봇 청소기의 시작점은 0번 인덱스에, 더러운 칸은 이후에 하나씩 순서대로 배열에 추가
                if(map[row][col] == 'o') massedLoc[0] = new Loc(row, col);
                else if(map[row][col] == '*') massedLoc[massedNum++] = new Loc(row, col);
            }
        }
    }

    static void solution() {
        // 로봇 청소기의 시작점 및 더러운 칸들 사이의 거리를 나타내는 배열
        distance = new int[massedNum][massedNum];
        // 각기 다른 두 지점 사이에 거리를 BFS를 통해 구한다
        for(int start = 0; start < massedNum; start++) {
            for(int end = start + 1; end < massedNum; end++) {
                int dist = bfs(massedLoc[start], massedLoc[end]);
                // 만약 구한 거리가 -1이라면 현재 시작 지점에서 끝 지점으로 도달할 수 없음을 의미한다
                // 방문할 수 없는 더러운 칸이 존재하니 -1을 출력한다
                if(dist == -1) {
                    sb.append(-1).append('\n');
                    return;
                } else { // 도달할 수 있다면 distance 배열을 해당 값으로 갱신
                    distance[start][end] = distance[end][start] = dist;
                }
            }
        }

        // 로봇 청소기의 시작점 및 더러운 칸들 사이의 거리를 구하였으니 이를 이용하여
        // 더러운 지점을 백트래킹을 통해 각 순서로 방문했을 때 필요한 이동 횟수를 구하고
        // 그 중 최소값을 구한다
        boolean[] selected = new boolean[massedNum];
        dfs(0, 0, 0, selected);

        sb.append(min).append('\n');
    }

    // 백트래킹을 통한 최소 이동 횟수를 구하는 메서드
    static void dfs(int index, int count, int totalDist, boolean[] selected) {
        if(count == massedNum - 1) { // 모든 더러운 칸을 다 방문했다면 이동 횟수의 최솟값 갱신
            min = Math.min(min, totalDist);
            return;
        }

        // 백트래킹을 통해 더러운 칸 방문
        for(int idx = 1; idx < massedNum; idx++) {
            if(!selected[idx]) {
                selected[idx] = true;
                dfs(idx, count + 1, totalDist + distance[index][idx], selected);
                selected[idx] = false;
            }
        }
    }

    // 서로 다른 두 지점 사이의 거리를 구하는 메서드
    static int bfs(Loc start, Loc end) {
        int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
        boolean[][] visited = new boolean[h][w];
        Queue<Loc> queue = new LinkedList<>();

        queue.offer(start);
        visited[start.x][start.y] = true;
        map[start.x][start.y] = '.';

        int moveNum = 0;
        while(!queue.isEmpty()) {
            // 이동 횟수별로 탐색하기 위해 현재 queue에 있는 칸들을 탐색하고
            // 모두 탐색했으면 이동 횟수를 1 늘려준다
            int curSize = queue.size();
            for(int idx = 0; idx < curSize; idx++) {
                Loc cur = queue.poll();
                // 목적지에 도달했다면 그때까지의 이동 횟수를 반환한다
                if(cur.x == end.x && cur.y == end.y)
                    return moveNum;

                // 도달하지 못했다면 인접한 곳을 탐색하여 이동할 수 있는 곳인지 확인하고
                // 이동할 수 있다면 방문 체크를 하고 이후 탐색을 위해 Queue에 해당 위치를 넣는다
                for(int dir = 0; dir < 4; dir++) {
                    int cx = cur.x + dx[dir], cy = cur.y + dy[dir];
                    if(isInMap(cx, cy)) {
                        if(!visited[cx][cy] && map[cx][cy] != 'x') {
                            visited[cx][cy] = true;
                            queue.offer(new Loc(cx, cy));
                        }
                    }
                }
            }

            // 현재 이동 횟수에서의 모든 탐색을 마쳤으니 이동 횟수를 1 증가시킨다
            moveNum++;
        }

        // 여기까지 도달했다면 결국 목적지까지 도달하지 못했다는 뜻이므로 -1을 반환한다
        return -1;
    }

    static boolean isInMap(int x, int y) {
        return x >= 0 && x < h && y >= 0 && y < w;
    }

    static class Loc {
        int x, y;

        public Loc(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) {
        while(true) {
            input();
            solution();
        }
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }

            return str;
        }
    }
}