065 : 다리 만들기

(Briefing)
(문제)	(단 하나의 맥락)	(입출력과 되어야 하는 그림)
다리는 2 이상, 직선, 섬의 개수는 2~6 모든 섬을 연결하는 다리의 최소 길이를 구하라	BFS + 최소 신장 트리	I // 지도 세로크기 N - 가로 크기 M (1)섬과 바다 정보 1,0 > M개 ... (N)섬과 바다 정보 O // 모든 다리 합의 최소 길이 출력 연결 불가시 -1 출력

 

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

public class Main {

    // point recognition
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};

    // box recognition
    static int[] label;
    static int[][] map;
    static int N, M, sNum;
    static boolean[][] visited; // phase checker
    static ArrayList<ArrayList<int[]>> sumlist;
    static ArrayList<int[]> mlist;
    static PriorityQueue<bEdge> queue;

    public static void main(String[] args) throws IOException {
        // Input Supply Cable
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // box recognition
        map = new int[N][M];
        visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // Operating BFS
        sNum = 1;
        sumlist = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != 0 && !visited[i][j]) {
                    BFS(i, j);
                    sNum++;
                    sumlist.add(mlist);
                }
            }
        }

        // point recognition : Edge preparing up
        queue = new PriorityQueue<>();
        for (int i = 0; i < sumlist.size(); i++) {

            ArrayList<int[]> now = sumlist.get(i);

            for (int j = 0; j < now.size(); j++) {

                int r = now.get(j)[0];
                int c = now.get(j)[1];
                int now_S = map[r][c];

                for (int d = 0; d < 4; d++) {
                    int tempR = dr[d];
                    int tempC = dc[d];
                    int length = 0;
                    while (r + tempR >= 0 && r + tempR < N && c + tempC >= 0 && c + tempC < M) {
                        if (map[r + tempR][c + tempC] == now_S)
                            break;
                        else if (map[r + tempR][c + tempC] != 0) {
                            if (length > 1)
                                queue.add(new bEdge(now_S, map[r + tempR][c + tempC], length));
                            break;
                        } else
                            length++;
                        if (tempR < 0)
                            tempR--;
                        else if (tempR > 0)
                            tempR++;
                        else if (tempC < 0)
                            tempC--;
                        else if (tempC > 0)
                            tempC++;
                    }
                }
            }
        }

        // Operating Minimum-spanning TREe
        label = new int[sNum];
        for (int i = 0; i < label.length; i++) {
            label[i] = i;
        }
        int usedEdge = 0;
        int plate = 0;
        while (!queue.isEmpty()) {
            bEdge now = queue.poll();
            if (find(now.s) != find(now.e)) {
                union(now.s, now.e);
                plate = plate + now.v;
                usedEdge++;
            }
        }
        if (usedEdge == sNum - 2) {
            System.out.println(plate);
        }  else  {
            System.out.println(-1);
        }
    }
    
    // External Module : Union
    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            label[b] = a;
        }
    }
    
    // External Module : find
    public static int find(int a) {
        if (a == label[a])
            return a;
        else 
            return label[a] = find(label[a]);
    }
    

    // External module : BFS
    private static void BFS(int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        mlist = new ArrayList<>();
        int[] start = {i, j};
        queue.add(start);
        mlist.add(start);
        visited[i][j] = true;
        map[i][j] = sNum;
        while (!queue.isEmpty()) {
            int now[] = queue.poll();
            int r = now[0];
            int c = now[1];
            for (int d = 0; d < 4; d++) {
                int tempR = dr[d];
                int tempC = dc[d];
                while (r + tempR >= 0 && r + tempR < N && c + tempC >= 0 && c + tempC < M) {
                    if (visited[r+tempR][c+tempC] == false && map[r + tempR][c + tempC] != 0) {
                        addNode(r + tempR, c + tempC, queue);
                    } else {
                        break;
                    }
                    if (tempR < 0)
                        tempR--;
                    else if (tempR > 0)
                        tempR++;
                    else if (tempC < 0)
                        tempC--;
                    else if(tempC > 0)
                        tempC++;
                }
            }
        }
    }

    // External Module island-info
    private static void addNode(int i, int j, Queue<int[]> queue) {
        map[i][j] = sNum;
        visited[i][j] = true;
        int[] temp = {i, j};
        mlist.add(temp);
        queue.add(temp);
    }
}

// External Class
class bEdge implements Comparable<bEdge> {
    int s, e, v;
    bEdge(int s, int e,int v) {
        this.s = s;
        this.e = e;
        this.v = v;
    }
    @Override
    public int compareTo(bEdge o) {
        return this.v - o.v;
    }
}