[백준]#1944 복제 로봇

문제

세준이는 어느 날 획기적인 로봇을 한 개 개발하였다. 그 로봇은 복제 장치를 이용하면 자기 자신을 똑같은 로봇으로 원하는 개수만큼 복제시킬 수 있다. 세준이는 어느 날 이 로봇을 테스트하기 위하여 어떤 미로에 이 로봇을 풀어 놓았다. 이 로봇의 임무는 미로에 흩어진 열쇠들을 모두 찾는 것이다. 그리고 열쇠가 있는 곳들과 로봇이 출발하는 위치에 로봇이 복제할 수 있는 장치를 장착해 두었다.

N*N의 정사각형 미로와 M개의 흩어진 열쇠의 위치, 그리고 이 로봇의 시작 위치가 주어져 있을 때, 모든 열쇠를 찾으면서 로봇이 움직이는 횟수의 합을 최소로 하는 프로그램을 작성하여라. 로봇은 상하좌우 네 방향으로 움직이며, 로봇이 열쇠가 있는 위치에 도달했을 때 열쇠를 찾은 것으로 한다. (복제된 로봇이어도 상관없다) 하나의 칸에 동시에 여러 개의 로봇이 위치할 수 있으며, 로봇이 한 번 지나간 자리라도 다른 로봇 또는 자기 자신이 다시 지나갈 수 있다. 복제에는 시간이 들지 않으며, 로봇이 움직이는 횟수의 합은 분열된 로봇 각각이 움직인 횟수의 총 합을 말한다. 복제된 로봇이 열쇠를 모두 찾은 후 같은 위치로 모일 필요는 없다.

입력

첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어진다. 1은 미로의 벽을 의미하고, 0은 지나다닐 수 있는 길, S는 로봇이 출발하는 위치, K는 열쇠의 위치가 주어진다. S는 1개, K는 M개가 주어진다. S와 K에서만 복제를 할 수 있음에 유의한다.

출력

첫째 줄에 모든 로봇이 움직인 횟수의 총 합을 출력한다. 모든 열쇠를 찾는 것이 불가능한 경우 횟수 대신 첫째 줄에 -1을 출력하면 된다.

예제 입력 1

5 2
11111
1S001
10001
1K1K1
11111

예제 출력 1

6

풀이

이 문제는 최소 스패닝 트리 문제로 프림 알고리즘과 크루스칼 알고리즘을 이용해서 풀 수 있었다. 간선이 많아서 인지 프림 알고리즘이 조금 더 시간이 적게 들었다. 프림 알고리즘에 간선의 길이는 BFS(너비 우선 탐색) 알고리즘을 이용해서 구했다.

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

public class Main {
    static char[][] map;
    static int[][] keys_num;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static ArrayList<Pair>[] list;
    static HashSet<Pair> keys = new HashSet<>();
    static int N;
    static int M;
    static boolean[] v;
    static int cnt;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        map = new char[N][N];
        keys_num = new int[N][N];
        list = new ArrayList[M+1];
        for(int i=0; i<=M; i++)
            list[i] = new ArrayList<>();
        int idx = 0;
        v = new boolean[M+1];
        cnt = M;

        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<N; j++) {
                map[i][j] = str.charAt(j);
                if(map[i][j]=='S' || map[i][j]=='K') {
                    keys_num[i][j] = idx;
                    keys.add(new Pair(i, j, 0));
                    idx++;
                }
            }
        }

        Iterator iter = keys.iterator();
        while(iter.hasNext()) {
            Pair p = (Pair)iter.next();
            bfs(p, keys_num[p.start][p.end]);
        }

        for(int i=0; i<=M; i++) {
            if(!v[i]) {
                System.out.println(-1);
                return;
            }
        }

        int ans = prim();

        if(cnt!=0)
            System.out.println(-1);
        else
            System.out.println(ans);
    }

    public static void bfs(Pair start, int x) {
        Queue<Pair> queue = new LinkedList<>();
        boolean[][] visited = new boolean[N][N];
        queue.add(start);
        visited[start.start][start.end] = true;

        while(!queue.isEmpty()) {
            Pair temp = queue.poll();

            if(map[temp.start][temp.end]=='K' || map[temp.start][temp.end]=='S') {
                int y = keys_num[temp.start][temp.end];
                list[x].add(new Pair(x, y, temp.cost));
                v[y] = true;
            }

            for(int i=0; i<4; i++) {
                int X = temp.start+dx[i];
                int Y = temp.end+dy[i];

                if(map[X][Y]=='1' || visited[X][Y]) continue;

                visited[X][Y] = true;
                queue.add(new Pair(X, Y, temp.cost+1));
            }
        }
    }

    public static int prim() {
        PriorityQueue<Pair> pq = new PriorityQueue<>();
        boolean[] visited = new boolean[M+1];
        ArrayList<Pair> tempList;
        Pair tempPair;
        Queue<Integer> queue = new LinkedList<>();
        int answer = 0;

        queue.add(0);
        while(!queue.isEmpty()) {
            int currentNode = queue.poll();
            visited[currentNode] = true;
            tempList = list[currentNode];

            for(int i=0; i<tempList.size(); i++) {
                if(!visited[tempList.get(i).end]) {
                    pq.add(tempList.get(i));
                }
            }

            while(!pq.isEmpty()) {
                tempPair = pq.poll();

                if(!visited[tempPair.end]) {
                    visited[tempPair.end]=true;
                    cnt--;
                    answer += tempPair.cost;
                    queue.add(tempPair.end);
                    break;
                }
            }
        }

        return answer;
    }

    public static class Pair implements Comparable<Pair>{
        int start;
        int end;
        int cost;

        public Pair(int start, int end, int cost) {
            this.start = start;
            this.end = end;
            this.cost = cost;
        }

        @Override
        public int compareTo(Pair p) {
            return this.cost > p.cost ? 1 : -1;
        }
    }
}