[백준]1944: 복제 로봇 - JAVA

[백준]1944: 복제 로봇

1944번: 복제 로봇

풀이

🪑 이 문제는 어떻게 풀어야 하는지 도저히 모르겠었던 문제였다! 

로봇이 움직이는 횟수의 합을 최소로 하기 위해서 BFS를 떠올렸지만, K를 만날 때마다 복제가 된다는 조건 때문에 방문 체크를 어떻게 처리해야 할지 걱정되었던 문제였다.

그래서 문제의 '알고리즘 분류'에서 MST라는 힌트를 얻었다. 막상 MST라는걸 알고 나니 되게 쉽게 느껴졌던 문제였다.

 

📝 문제를 정리해 보자!

• 모든 열쇠를 찾으면서 로봇이 움직이는 횟수의 합을 최소로 해야 한다,
• 로봇은 상 하 좌 우로 이동한다.
• 하나의 칸에 여러 로봇이 존재할 수 있다.
• 현재 칸이 S와 K일때 로봇을 복제할 수 있다.

 

 

🔧 문제를 풀어보자!

1.  S또는 K의 위치를 저장한다.
2.  S또는 K에서 또 다른 S또는 K로 가는 모든 최단 경로를 찾아준다.
3.  해당 경로를 사용해서 MST를 구한다.

 

 

🔹 S또는 K의 위치를 저장한다.

- S와 K를 시작으로 모든 최단 경로를 계산해 줄 것이기 때문이다.

- ArrayList에 담아주었다. 이때 인덱스가 해당 S또는 K노드의 번호가 된다.

 

🔹 S또는 K에서 또 다른 S또는 K로 가는 모든 최단 경로를 찾아준다.

- ArrayList에서 하나씩 꺼내어 해당 노드에서 부터 다른 S또는 K가 있는 노드로 가는 모든 최단경로를 계산한다.

- 이때 모든 최단거리의 정보를 거리 순서대로 내림차순하도록 Override되어 있는 PriorityQueue에 담아준다.

 

🔹 해당 경로를 사용해서 MST를 구한다.

- Kruskal을 사용하여 얻은 모든 간선 중에서 최단 거리를 갖는 간선들을 선택해 주면 된다.

- 이때 선택한 간선의 개수가 m개가 아니라면 MST를 완성하지 못한 것이므로 -1을 return하도록 한다.

 

 

 

코드

//1944: 복제 로봇
import java.io.*;
import java.util.*;
 
public class Main {
 
    static ArrayList<Node> list;
    static int n, m;
    static char[][] board;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static PriorityQueue<Mst_Node> pq;
    static int[] parent;
 
    public static void main(String[] args) throws IOException {
 
        //입력
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
        String str = bf.readLine();
        StringTokenizer st = new StringTokenizer(str);
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
 
        board = new char[n][n];
        list = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            str = bf.readLine();
            for(int j = 0; j < n; j++) {
                char c = str.charAt(j);
                board[i][j] = c;
                if(c == 'S' || c == 'K') list.add(new Node(i, j, 0));
            }
        }
        //입력 끝
 
        pq = new PriorityQueue<Mst_Node>();
        for(int i = 0; i < m + 1; i++) {
            bfs(i);
        }
        System.out.println(kruskal());
    }   
 
    public static int kruskal() {
        parent = new int[m + 1];
        for(int i = 0; i < m + 1; i++) {
            parent[i] = i;
        }
 
        int cost = 0;
        int edge_count = 0;
        while(!pq.isEmpty()) {
            Mst_Node current = pq.poll();
            
            int p1 = find(current.s);
            int p2 = find(current.e);
 
            if(p1 != p2) {
                union(p1, p2);
                cost += current.cost;
                edge_count++;
            }
        }
        if(edge_count != m) return -1; //모두 연결되지 않으면 안됨.
        return cost;
    }
 
    public static void union(int p1, int p2) {
        parent[p1] = p2;
    }
 
    public static int find(int node) {
        if(parent[node] == node) return node;
        else return parent[node] = find(parent[node]);
    }
 
    public static void bfs(int num) {
        Queue<Node> q = new LinkedList<>();
        boolean[][] visited = new boolean[n][n];
        q.offer(list.get(num));
        visited[list.get(num).x][list.get(num).y] = true;
 
        while(!q.isEmpty()) {
            Node current = q.poll();
 
            for(int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];
 
                if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                if(board[nx][ny] == '1' || visited[nx][ny]) continue;
                visited[nx][ny] = true;
 
                if(board[nx][ny] == 'S' || board[nx][ny] == 'K') {
                    for(int j = 0; j < m + 1; j++) {
                        if(list.get(j).x == nx && list.get(j).y == ny) {
                            pq.offer(new Mst_Node(num, j, current.count + 1));
                        }
                    }
                }
                q.offer(new Node(nx, ny, current.count + 1));
            }
        }
    }
 
    public static class Mst_Node implements Comparable<Mst_Node> {
        int s, e, cost;
 
        public Mst_Node(int s, int e, int cost) {
            this.s = s;
            this.e = e;
            this.cost = cost;
        }
 
        @Override
        public int compareTo(Mst_Node n) {
            return this.cost - n.cost;
        }
    }
 
    public static class Node {
        int x, y, count;
 
        public Node(int x, int y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }
}