[BOJ] 백준 1944 : 복제 로봇 (java)

🧪 1944 복제 로봇

---

난이도 : 🌟 골드 1
유형 : 크루스칼

https://www.acmicpc.net/problem/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. 미로의 정보를 채우고, 시작점(S)과 열쇠(K)의 위치를 저장한다.

 

2. BFS를 이용해 각 시작점(S 또는 K)에서 다른 모든 시작점으로의 최단 거리를 계산하여 그래프를 구성한다.

 

3. 계산된 최단 거리 정보를 Vertex 객체로 표현하고, 우선순위 큐에 삽입하여 오름차순으로 정렬된 상태를 유지한다.

 

4. 크루스칼 알고리즘을 이용해 최소 스패닝 트리를 만든다. 이 과정에서 사이클을 방지하기 위해 find와 union 연산을 사용한다.

 

5. 연결된 간선의 개수가 열쇠의 개수(M)와 다르면 모든 점을 연결할 수 없으므로 -1을 반환한다.

 

6. 연결된 간선이 열쇠 개수와 같다면 최소 비용으로 모든 점을 연결한 총 거리를 반환한다.

 

💻 최종 코드 (388 ms)

---

import java.util.*;
import java.io.*;

public class Main {

    static class Node {

        int x, y, dis;

        Node (int x, int y, int dis) {
            this.x = x;
            this.y = y;
            this.dis = dis;
        }
    }

    static class Vertex implements Comparable<Vertex> {

        int s, e, edge;

        Vertex(int s, int e, int edge) {
            this.s = s;
            this.e = e;
            this.edge = edge;
        }

        @Override
        public int compareTo(Vertex o) {
            return this.edge - o.edge;
        }
    }

    static BufferedReader br;
    static int n, m;
    static char[][] maze;
    static boolean[][] visited;
    static List<Node> nodes;
    static PriorityQueue<Vertex> vertexes;
    static int[] parent;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    public static void main(String[] args) throws Exception {

//      br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new FileReader("input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        nodes = new ArrayList<>();
        vertexes = new PriorityQueue<>();

        fillMaze();

        for (int i = 0; i < m + 1; i++) {
            bfs(i);
        }

        System.out.println(kruskal());

        br.close();
    }

    private static void fillMaze() throws Exception {

        maze = new char[n][n];
        for (int i = 0; i < n; i++) {
            char[] words = br.readLine().toCharArray();
            for (int j = 0; j < n; j++) {
                maze[i][j] = words[j];

                if (maze[i][j] == 'S' || maze[i][j] == 'K') {
                    nodes.add(new Node(i, j, 0));
                }
            }
        }
    }

    private static void bfs(int start) {

        Queue<Node> q = new LinkedList<>();
        q.add(nodes.get(start));
        visited = new boolean[n][n];
        visited[nodes.get(start).x][nodes.get(start).y] = true;

        while (!q.isEmpty()) {
            Node curNode = q.poll();

            for (int i = 0; i < 4; i++) {
                int nx = curNode.x + dx[i];
                int ny = curNode.y + dy[i];

                if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                if (maze[nx][ny] == '1' || visited[nx][ny]) continue;

                if (maze[nx][ny] == 'S' || maze[nx][ny] == 'K') {
                    for (int j = 0; j < m + 1; j++) {
                        if (nodes.get(j).x == nx && nodes.get(j).y == ny) {
                            vertexes.add(new Vertex(start, j, curNode.dis + 1));
                        }
                    }
                }

                visited[nx][ny] = true;
                q.add(new Node(nx, ny, curNode.dis + 1));
            }
        }
    }

    private static int kruskal() {

        parent = new int[m + 1];
        for (int i = 0; i < m + 1; i++) {
            parent[i] = i;
        }

        int totalDis = 0;
        int edgeCount = 0;
        while (!vertexes.isEmpty()) {
            Vertex curVertex = vertexes.poll();

            if (find(curVertex.s) != find(curVertex.e)) {
                union(curVertex.s, curVertex.e);
                totalDis += curVertex.edge;
                edgeCount++;
            }
        }

        if (edgeCount != m) return -1;
        return totalDis;
    }

    private static void union(int x, int y) {

        x = find(x);
        y = find(y);

        if (x != y) {
            parent[y] = x;
        }
    }

    private static int find(int x) {

        if (x == parent[x]) {
            return x;
        }

        return parent[x] = find(parent[x]);
    }
}