[백준] 1944번 : 복제 로봇

1944번: 복제 로봇

---

[BFS * m회 + Kruskal (=Union-Find, Sort)]

 

어느정도 발상의 전환이 필요한 문제라고 생각된다. 'S'에서부터 'K'를 찾아가는 것이 아닌 각각의 'K'에서 또다른 'K'나 'S'를 찾아가는 방법으로 풀어보았다. 그러므로 m개의 'K'가 주어지면, 각각의 'K'의 위치에서 BFS를 수행하며 다른 'K'나 'S'를 만날 때 간선의 정보를 만들어 List에 담아주었다.

 

이 때 크루스칼 알고리즘을 수행하려면 출발 정점과 도착 정점의 정보 그리고 가중치(weight)가 있어야 한다. 그래서 각 'K' 정점의 인덱스는 따로 2차원 배열 idxTable[ ][ ]에 담아주었다.

        for(int i=1, k=1; i<=n; i++){
            char[] str = br.readLine().toCharArray();
            for(int j=1; j<=n; j++){
                map[i][j] = str[j-1];

                if(map[i][j] == 'K') {
                    keys[k] = new Point(i, j, 0, k); //'K'의 대한 정보를 구조체로 작성
                    idxTable[i][j] = k++; //'K'를 입력받을 때 마다 idxTable에 'K'에 대한 인덱스 생성
                }
            }
        }

 

 

 

그렇다면 '-1'을 출력해야하는 시점은 언제일까? 아마 'K'에서 BFS를 수행했는데, 'S'를 만나지 못했다면. 그것은 'S'에서 'K'를 갈 수 없다는 것과 동일한 의미이므로 모든 키를 수집할 수 없게된다. 그래서 각 BFS 내부에서 'S'를 만나면 flag = true로 설정하고, BFS 종료 이후 flag == false이면 '-1'을 출력하고 종료하도록 설계했다.

 

        for(int i=1; i<=m; i++) {
            parent[i] = i;
            flag = false;

            BFS(keys[i]);
            if(!flag){ //K -> S 못가면 모든 키를 못찾는 것 이다.
                System.out.println(-1);
                System.exit(0);
            }
        }

마지막으로 BFS의 내부는 간결하다. 'S'의 인덱스는 항상 0으로 고정시켜놓고, 다른 'K'를 만나면 그 'K'의 인덱스를 idxTable에서 찾아 List에 간선 정보를 담아주면 된다.

    static void BFS(Point key){

        Queue<Point> Q = new LinkedList<>();

        int idx = key.idx;
        visit[key.y][key.x][idx] = true;
        Q.add(new Point(key.y, key.x, key.move, idx));

        while(!Q.isEmpty()){
            Point p = Q.poll();
            int y = p.y;
            int x = p.x;
            int move = p.move;

            for(int a=0; a<4; a++){
                int ny = y+Y[a];
                int nx = x+X[a];

                if(ny < 1 || nx < 1 || ny > n || nx > n || visit[ny][nx][idx] || map[ny][nx] == '1') continue;

                visit[ny][nx][idx] = true;
                
                //Edge(출발 정점, 도착 정점, 가중치)
                if(map[ny][nx] == 'S') {
                    list.add(new Edge(idx, 0, move + 1));
                    flag = true;
                }
                else if(map[ny][nx] == 'K')
                    list.add(new Edge(idx, idxTable[ny][nx], move + 1)); //idxTable은 방문한 K가 몇번 째 K인지 저장

                Q.add(new Point(ny, nx, move + 1, idx));
            }
        }
    }

# Code </>

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

public class Main {

    static class Point{
        int y, x, move, idx;
        public Point(int yy, int xx, int m, int i){
            y=yy;
            x=xx;
            move = m;
            idx=i;
        }
    }
    static class Edge implements Comparable<Edge>{
        int h, tg, move;
        public Edge(int home, int t, int m){
            h=home;
            tg=t;
            move=m;
        }

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

    static boolean[][][] visit = new boolean[251][251][251];
    static List<Edge> list = new ArrayList<>();
    static char[][] map = new char[51][51];
    static int[][] idxTable = new int[51][51];
    static int n;
    static boolean flag;

    static int[] parent = new int[251], Y = {-1, 1, 0, 0}, X = {0, 0, -1, 1};

    static int getParent(int x){
        if(parent[x] == x) return x;
        return parent[x] = getParent(parent[x]);
    }
    static boolean findParent(int a, int b){
        a = getParent(a);
        b = getParent(b);

        return a == b? true:false;
    }
    static void union(int a, int b){
        a = getParent(a);
        b = getParent(b);

        if(a < b) parent[b] = a;
        else parent[a] = b;
    }

    static void BFS(Point key){

        Queue<Point> Q = new LinkedList<>();

        int idx = key.idx;
        visit[key.y][key.x][idx] = true;
        Q.add(new Point(key.y, key.x, key.move, idx));

        while(!Q.isEmpty()){
            Point p = Q.poll();
            int y = p.y;
            int x = p.x;
            int move = p.move;

            for(int a=0; a<4; a++){
                int ny = y+Y[a];
                int nx = x+X[a];

                if(ny < 1 || nx < 1 || ny > n || nx > n || visit[ny][nx][idx] || map[ny][nx] == '1') continue;

                visit[ny][nx][idx] = true;

                if(map[ny][nx] == 'S') {
                    list.add(new Edge(idx, 0, move + 1));
                    flag = true;
                }
                else if(map[ny][nx] == 'K')
                    list.add(new Edge(idx, idxTable[ny][nx], move + 1)); //idxTable은 방문한 K가 몇번 째 K인지 저장

                Q.add(new Point(ny, nx, move + 1, idx));
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        Point[] keys = new Point[m+1];

        for(int i=1, k=1; i<=n; i++){
            char[] str = br.readLine().toCharArray();
            for(int j=1; j<=n; j++){
                map[i][j] = str[j-1];

                if(map[i][j] == 'K') {
                    keys[k] = new Point(i, j, 0, k);
                    idxTable[i][j] = k++;
                }
            }
        }

        for(int i=1; i<=m; i++) {
            parent[i] = i;
            flag = false;

            BFS(keys[i]);
            if(!flag){ //K -> S 못가면 모든 키를 못찾는 것 이다.
                System.out.println(-1);
                System.exit(0);
            }
        }

        //크루스칼 알고리즘 수행
        Collections.sort(list);

        int sum = 0;
        for(Edge e:list)
            if(!findParent(e.h, e.tg)){
                sum += e.move;
                union(e.h, e.tg);
            }
        System.out.println(sum);
    }
}