BOJ 1944 - 복제 로봇

1944번: 복제 로봇 (acmicpc.net)

 

모든 열쇠를 찾으면서 로봇이 움직이는 횟수의 합의 최소.

하나의 칸에 동시에 여러 로봇이 존재할 수 있다.

S와 K의 위치에서 로봇이 복제가 가능하다.

로봇은 최초에 1대 존재하며 S와 K에서 원하는 숫자만큼 복제할 수 있다.

→ 복제란 무엇이지? 최단 거리니 BFS를 생각해 보면 퍼저나 가는 모습이 마치 복제된 로봇들이 이동하는 것과 유사하다. 결국 복제는 하나의 로봇이 여러 경로로 갈 수 있다고 이야기하는 것 같다.

→ 특히 복제 한다는 부분에서 중요한 노드임을 판단할 수 있다.

결국 최단거리로 모든 열쇠를 수거해야 한다. 최단거리의 기반 알고리즘은 BFS로 하면 될 것 같다.

같은 지점을 반복해서 지나갈 수 있다.

→ 하였으므로 단순 배열로 방문 처리를 하면 안 된다. 경로 자체를 반복 가능한 간선으로 보고 각 노드를 방문 기준으로 처리해야 할 것 같다.

결국 노드와 간선으로 구성된 그래프 문제가 된다.

모든 노드를 최소 비용으로 연결하면 되는 문제가 되며 MST이다.

1. 입력을 순회하며 S, K 위치를 저장한다. = 노드가 된다.
2. 노드들 사이의 거리를 계산한다.
   1. 이게 곧 간선이다. 간선이니 시작, 도착, 거리 이렇게 세 필드가 필요하다.
   2. Edge라는 클래스에 저장하며 이 Edge들을 저장한다.
   3. 거리 계산은 한 노드에서 다른 노드들 사이 거리를 계산하는 것이다. bfs를 통해 계산한다.
3. 저장된 Edge들을 가지고 최소신장트리를 구성한다.
   1. 가장 비용(거리)이 저렴한 것부터 꺼내서 두 노드를 연결한다.
   2. 노드를 연결하는데 이미 같은 집합에 있다면 패스
      1. UNION-FIND를 통해 해결

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static FastReader scan = new FastReader();
    static int N, M;
    static int[][] DIRECTION = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static char[][] map;
    static Map<String, Point> points = new HashMap<>(); // 시작점, 열쇠들이 저장될 공간
    static int[][] distances;

    static class Point {
        int id, r, c;

        Point(int id, int r, int c) {
            this.id = id;
            this.r = r;
            this.c = c;
        }

        String getKey() {
            return r + "," + c;
        }

        @Override
        public boolean equals(Object o) {

            if (!(o instanceof Point)) {
                return false;
            }
            Point p = (Point) o;

            return this.r == p.r && this.c == p.c;
        }
    }

    static class Edge implements Comparable<Edge> {
        int start, end, weight;

        Edge(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            return this.weight - o.weight;
        }
    }

    static void input() {
        N = scan.nextInt();
        M = scan.nextInt();
        map = new char[N][N];
        int id = 0;
        for (int i = 0; i < N; i++) {
            map[i] = scan.next().toCharArray();
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 'S' || map[i][j] == 'K') {
                    Point point = new Point(id++, i, j);
                    points.put(point.getKey(), point);
                }
            }
        }

        int size = points.size();
        distances = new int[size][size];
        for (int[] row : distances) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
    }

    static void calculateDistances() {
        for (Point point : points.values()) {
            dfs(point);
        }
    }

    static void dfs(Point start) {
        Queue<Point> q = new LinkedList<>();
        int[][] visited = new int[N][N];
        q.add(start);
        visited[start.r][start.c] = 0;

        while (!q.isEmpty()) {
            Point curr = q.poll();
            // 시작점이 아니면서 다른 노드라면 거리 갱신
            if (!start.equals(curr) && points.containsKey(curr.getKey())) {
                int from = start.id;
                int to = points.get(curr.getKey()).id;
                int dist = visited[curr.r][curr.c];
                distances[from][to] = dist;
                distances[to][from] = dist;
            }

            for (int d = 0; d < 4; d++) {
                int nr = curr.r + DIRECTION[d][0];
                int nc = curr.c + DIRECTION[d][1];

                if (nr < 0 || nr >= N || nc < 0 || nc >= N) {
                    continue;
                }
                if (visited[nr][nc] != 0) {
                    continue;
                }
                if (map[nr][nc] == '1') {
                    continue;
                }

                q.add(new Point(-1, nr, nc));
                visited[nr][nc] = visited[curr.r][curr.c] + 1;
            }
        }
    }

    private static int getShortestPath() {
        PriorityQueue<Edge> edges = new PriorityQueue<>();
        for (int i = 0; i < points.size(); i++) {
            for (int j = i + 1; j < points.size(); j++) {
                if (distances[i][j] != Integer.MAX_VALUE) {
                    edges.add(new Edge(i, j, distances[i][j]));
                }
            }
        }
        int[] parent = new int[points.size()];
        for (int i = 0; i < points.size(); i++) {
            parent[i] = i;
        }
        int sum = 0;
        int connected = 0;
        while (!edges.isEmpty()) {
            Edge edge = edges.poll();
            int start = edge.start;
            int end = edge.end;

            if (find(parent, start) != find(parent, end)) {
                union(parent, start, end);
                sum += edge.weight;
                connected++;
            }
        }

        // 만약 모든 노드들을 연결하지 못했다면 -1 반환
        if (connected != points.size() - 1) {
            return -1;
        }
        return sum;
    }

    private static int find(int[] parent, int node) {
        if (parent[node] != node) {
            parent[node] = find(parent, parent[node]);
        }

        return parent[node];
    }

    private static void union(int[] parent, int node1, int node2) {
        int root1 = find(parent, node1);
        int root2 = find(parent, node2);

        if (root1 != root2) {
            parent[root1] = root2;
        }
    }

    public static void main(String[] args) {
        input();
        calculateDistances();
        int result = getShortestPath();
        System.out.println(result);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            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());
        }
    }
}