[JAVA] 최소 신장 트리 알고리즘 자바 백준 BOJ 1197, 17472, 1414

최소신장 트리

 

최소 신장 트리(Maximum Spanning Tree, MST)란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리입니다. 아래 특징을 가집니다.

 

• 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않음.
• N 개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1 개임.

 

최소 신장 트리 핵심 이론

1. 그래프 구현(에지 리스트), 유니온 파인드 배열 초기화

최소 신장 트리는 데이터를 노드가 아니라 에지를 중심으로 저장합니다. 그래서 벨만-포드 알고리즘에서처럼 에지 리스트의 형태로 저장해야 합니다. Edge 클래스는 일반적으로 노드 변수 2개, 가중치 변수 1개로 구성됩니다. 

사이클 처리를 위한 유니온 파인드 배열도 초기화해야 합니다. 배열의 인덱스를 해당 자리의 값을 초기화합니다.

 

2. 그래프 데이터를 가중치 기준으로 정렬

이 때 Comparable() 함수를 사용해서 가중치를 오름차순 정렬로 설정합니다.

 

3. 가중치가 낮은 에지부터 연결 시도하기

이 때 바로 연결하지 않고 이 에지를 선택했을 때 그래프에 사이클 형성 유무를 find 연산으로 확인한 후에 사이클이 형성되지 않을 때만 union 연산을 이용해서 두 노드를 연결합니다.

4. 위의 3의 과정을 반복

전체 노드가 N 개이면 연결한 에지의 개수가 N-1 이 될 때까지 반복합니다.

5. 총 에지 비용 출력

에지의 개수가 N -1 이 되면 알고리즘을 종료하고 총 에지 비용을 출력합니다.

 

 

 

최소 신장 트리는 에지를 기준으로 하는 알고리즘이므로 에지 리스트의 형태로 데이터를 담습니다.

또 사이클이 존재하면 안 된다는 특징을 가지고 있어 사이클 판별 알고리즘은 유니온 파인드 알고리즘을 내부에 구현해야 합니다.

 

백준 1197 최소 스패닝 트리

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

 

1. 문제 분석

위에서 설명한 최소 신장 트리의 핵심 이론대로 풀면 됩니다.

에지 리스트에 에지 데이터를 저장할 때 더 빠른 정렬을 위해서 PriorityQueue(우선순위 큐)를 사용하겠습니다.

2. 손으로 풀기

3. 슈도코드

V: 노드 개수, E: 에지 개수
pQu: 그래프의 에지를 저장할 우선순위 큐
parent: 부모 배열(대표노드 배열)
ans = 0
edgeCnt = 0

parent 의 배열 값을 각 인덱스와 똑같이 설정.
pQu 에 에지 데이터 입력받기 : 오름차순으로 저장 될것임.

while(edgeCnt < V-1)
    cur = pQu 에서 poll 한 것.
    if cur 의 노드1 과 노드2 가 서로 대표노드가 다르면
        노드1 과 노드2 의 부모노드를 똑같이 하기
        edgeCnt++;
        ans += cur의 가중치

ans 출력.


// union 함수
union(n1, n2){
    n1 = find(n1)
    n2 = find(n2)
    if n1 != n2 이면
        parent[n2] = n1;

// find 함수: 재귀 함수 형태
find(n){
    if n == 유니온 파인드배열[n]
        return n;
    else
        return parent[n] = find[parent[n]];
}



static class Edge implements Comparable{
    n1, n2, w

    // 정렬 함수
    w 을 기준으로 오름차순으로 정렬
}

4. 코드

public class BaekJun1197Self {

    static int V;
    static PriorityQueue<Edge> pQu;
    static int[] parent;
    static int ans, edgeCnt;

    public static void main(String[] args) throws IOException {
        input();
        mstFunc();
        System.out.println(ans);
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

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

        pQu = new PriorityQueue<>();
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            pQu.offer(new Edge(n1, n2, w));
        }
        br.close();
    }

    private static void mstFunc() {
        while (edgeCnt < V - 1) {
            Edge curEdge = pQu.poll();
            int n1Parent = find(curEdge.n1);
            int n2Parent = find(curEdge.n2);
            if (n1Parent != n2Parent) {
                parent[n2Parent] = n1Parent;
                edgeCnt++;
                ans += curEdge.w;
            }
        }
    }

    static int find(int n) {
        if (n == parent[n]) {
            return n;
        } else {
            return parent[n] = find(parent[n]);
        }
    }

    static class Edge implements Comparable<Edge> {
        int n1, n2, w;

        public Edge(int n1, int n2, int w) {
            this.n1 = n1;
            this.n2 = n2;
            this.w = w;
        }

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

 

백준 17472 다리 만들기 2

https://www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

 

1. 문제 분석

문제의 데이터의 크기는 매우 작아서 시간 복잡도는 여유 있습니다. 하지만 여러 단계로 나눠서 생각해야 하는 문제입니다.

 

a. 먼저 주어진 지도에서 섬으로 표현된 값을 각각의 섬마다 다르게 표현해야 합니다.

b. 이후 각 섬의 모든 위치에서 다른 섬으로 연결할 수 있는 에지가 있는지 확인해서 에지리스트를 만듭니다.

c. 마지막으로 최소 신장 트리를 적용하면 됩니다.

 

2. 손으로 풀기

a. BFS

지도의 정보를 2차원 배열에 저장하고 섬으로 표시된 모든 점에서 BFS 을 실행해서 섬을 구분합니다. (상, 하, 좌, 우 네 방향으로 탐색합니다.) 방문한 적이 없고 바다가 아닐 때 같은 섬으로 하면 됩니다.

 

 

b. 에지 리스트 만들기

모든 섬에서 상하좌우로 다리를 지어서 다른 섬으로 연결할 수 있는지 확인합니다.

연결할 곳이 현재 섬이면 탐색 중단, 바다라면 탐색을 계속 수행합니다.

다른 섬을 만났을 때 다리의 길이가 2 이상이면 이 다리를 에지 리스트에 추가합니다.

 

 

c. 최소 신장 트리 알고리즘 수행

전 단계에서 수집한 모든 에지를 오름차순으로 정렬해서 최소 신장 트리 알고리즘을 수행합니다.

 

 

3. 슈도코드

1. BFS 로 섬을 구분.
dx, dy: 네 방향 탐색을 위한 배열
N, M: 행렬의 크기
map: 맵 정보 저장 배열
visited: BFS 을 할 때 방문 여부 저장 배열
sumlist: 모든 섬 정보 저장
mlist: 한 개의 섬 정보 저장.

for(N)
    for(M)
        입력 데이터를 map 에 저장

for(i -> N)
    for(j -> M)
        BFS(i, j) // 모든 위치에서 BFS 을 실행해서 섬을 분리.
        결과를 sumlist 변수에 넣기

2. 에지(다리) 정보를 찾아내서 큐에 저장
queue: 다리 정보를 저장해 줄 큐. 우선순위 큐
for(i => sumlist 크기만큼)
    now = sumlist[i]
    for(j -> now 크기만큼)
        1개의 섬의 모든 위치에서 만들 수 있는 다리 정보를 저장.
        (상,하,좌,우 방향, 4방향 탐색. 그렇게 4개를 next 라고 하면)
         테두리에서 4방향 탐색을 해야 함.

         next 가 같은 섬이면 안됨.
         다른 섬이라면 (같은 섬도 아니고 바다도 아니라면)
            만약 다리 길이(출발 섬으로부터의 거리)가 2 이상이면
                큐에 해당 에지 정보를 넣기
        바다라면
            다리 길이를 연장

3. MST 최소 신장 트리 알고리즘 수행.
parent: 대표 노드 저장 배열
대표 노드 저장 배열 값을 자기 자신의 indx 로 초기화.
while (큐가 빌 때까지) {
    큐에서 에지 정보를 가져오기
    if 에제의 두 노드를 연결해도 사이클이 생기지 않으면(== 부모 노드가 다르면)
        union 연산
        에지의 가중치를 정답 변수에 더하기
}

사용한 에지가 노드 개수 - 1 만큼이면 가중치의 합을 결과로 출력.
아니면 -1 출력.


// 1-1. static 메서드 BFS
BFS(i, j)
    큐에 [i, j] 노드 넣기. 방문 체크. map 에 현재 섬의 값 저장해서 구분해주기.
    i, j 위치에서 네 방향을 탐색해서 1 개 섬의 영역을 저장.

    다음 위치 next(4개)에 대해 방문한 적이 없고 바다가 아니라면
        같은 섬이다. map 에 값을 섬의 값을 저장해서 구분해주기
        방문 체크.
        next 을 저장해두기, queue 에 넣다리 정보

// 2-1 static class Edge
Edge implements Comparable {
    n1, n2, weight,
    정렬 기준은 가중치의 오름차순.
}

// 3-1. union, find 함수
union(n1, n2){
    find(n1), find(n2) 을 비교
    대표 노드 끼지 연결.
}
find(n){ // 재귀형태
    if(n 이 대표노드면) 리턴
    아니면 return parent(n) = find(parent[n]);
}

4. 코드

public class BaekJun17472 {

    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    static int[][] map;
    static int N, M, islandNum;
    static boolean[][] visited;
    static ArrayList<ArrayList<int[]>> sumlist;
    static ArrayList<int[]> mlist;
    static int[] parent;
    static boolean canConnect;

    public static void main(String[] args) throws IOException {
        input();

        // 1. BFS 로 각 섬을 구분한다.
        classifyIslands();

        // 2. 각 섬에서 다른 섬으로 연결할 수 있는 에지를 확인, 에지 리스트를 만든다.
        PriorityQueue<Edge> pqu = getAllBridges();

        // 3. 최소신장트리(MST) 을 적용
        int ans = mstAlgorithm(pqu);

        output(ans);
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 세로
        M = Integer.parseInt(st.nextToken()); // 가로
        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());
            }
        }
    }

    private static void classifyIslands() {
        islandNum = 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]) {
                    bfsFunc(i, j);
                    islandNum++;
                    sumlist.add(mlist);
                }
            }
        }
    }

    // 1. bfs
    static void bfsFunc(int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        mlist = new ArrayList<>();
        int[] start = {i, j};
        queue.offer(start);
        mlist.add(start);
        visited[i][j] = true;
        map[i][j] = islandNum;

        while (!queue.isEmpty()) {
            int now[] = queue.poll();
            int row = now[0];
            int col = now[1];
            for (int d = 0; d < 4; d++) {
                int tempRow = dr[d];
                int tempCol = dc[d];
                int nextRow = row + tempRow;
                int nextCol = col + tempCol;
                while (nextRow >= 0 && nextRow < N && nextCol >= 0 && nextCol < M) {
                    if (!visited[nextRow][nextCol] && map[nextRow][nextCol] != 0) {
                        map[nextRow][nextCol] = islandNum;
                        visited[nextRow][nextCol] = true;
                        int[] temp = {nextRow, nextCol};
                        mlist.add(temp);
                        queue.offer(temp);
                    } else {
                        break;
                    }
                    if (tempRow > 0) tempRow++;
                    else if (tempRow < 0) tempRow--;
                    else if (tempCol > 0) tempCol++;
                    else if (tempCol < 0) tempCol--;
                    nextRow = row + tempRow;
                    nextCol = col + tempCol;
                }

            }
        }


    }

    // 2. Edge 리스트 만들 때 사용
    static class Edge implements Comparable<Edge> {
        int n1, n2, weight;

        public Edge(int n1, int n2, int weight) {
            this.n1 = n1;
            this.n2 = n2;
            this.weight = weight;
        }

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



    }
    private static PriorityQueue<Edge> getAllBridges() {
        PriorityQueue<Edge> pqu = new PriorityQueue();
        for (ArrayList<int[]> nowIsland : sumlist) {
            for (int[] islandIndex : nowIsland) {
                int rowInd = islandIndex[0];
                int colInd = islandIndex[1];
                int nowIslandNum = map[rowInd][colInd];
                for (int d = 0; d < 4; d++) {
                    int dRow = dr[d];
                    int dCol = dc[d];
                    int bridgeLen = 0;
                    int nextRow = rowInd + dRow;
                    int nextCol = colInd + dCol;
                    while (nextRow >= 0 && nextCol >= 0 && nextRow < N && nextCol < M) {
                        int nextIslandNum = map[rowInd + dRow][colInd + dCol];
                        if (nextIslandNum == nowIslandNum) {
                            break;
                        } else if (nextIslandNum != 0) {
                            if (bridgeLen > 1) {
                                pqu.add(new Edge(nowIslandNum, nextIslandNum, bridgeLen));
                            }
                            break;
                        } else {
                            bridgeLen++;
                        }
                        if (dRow < 0) dRow--;
                        else if (dRow > 0) dRow++;
                        else if (dCol < 0) dCol--;
                        else if (dCol > 0) dCol++;
                        nextRow = rowInd + dRow;
                        nextCol = colInd + dCol;
                    }
                }
            }
        }
        return pqu;
    }


    // 3. MST
    private static int mstAlgorithm(PriorityQueue<Edge> pqu) {
        parent = new int[islandNum];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
        int ans = 0;
        int edgeCnt = 0;
        while (!pqu.isEmpty()) {
            Edge curEdge = pqu.poll();
            int n1 = find(curEdge.n1);
            int n2 = find(curEdge.n2);
            if (n1 != n2) {
                parent[n2] = n1;
                edgeCnt++;
                ans += curEdge.weight;
            }
            if (edgeCnt == islandNum - 2) {
                canConnect = true;
                break;
            }
        }
        return ans;
    }
    static int find(int n) {
        if (n == parent[n]) {
            return n;
        } else {
            return parent[n] = find(parent[n]);
        }
    }


    private static void output(int ans) {
        if (canConnect) {
            System.out.println(ans);
        } else {
            System.out.println(-1);
        }
    }
}

 

비슷하지만 조금 다른 풀이

public class BaekJun17472 {
    static int N, M, islandNum;
    static int[] dRow = {-1, 0, 1, 0};
    static int[] dCol = {0, -1, 0, 1};
    static int[][] map;
    static boolean[][] visited;
    static ArrayList<RowAndCol> islandIndexList;
    static ArrayList<ArrayList<RowAndCol>> sumList;
    static ArrayList<RowAndCol> mList;
    static int[] parent;
    static int ans;
    static boolean canConnect;

    public static void main(String[] args) throws IOException {
        input();
        classifyIsland();
        PriorityQueue<Edge> pqueue = getEdges();
        mstFunc(pqueue);
        output();
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        visited = new boolean[N][M];
        islandIndexList = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                int tmp = Integer.parseInt(st.nextToken());
                map[i][j] = tmp;
                if (tmp == 1) {
                    islandIndexList.add(new RowAndCol(i, j));
                }
            }
        }
    }

    private static void classifyIsland() {
        islandNum = 0;
        Queue<RowAndCol> queue = new LinkedList();
        sumList = new ArrayList<>();
        for (RowAndCol island : islandIndexList) {
            mList = new ArrayList<>();
            if (!visited[island.row][island.col]) {
                queue.offer(island);
                visited[island.row][island.col] = true;
                islandNum++;
            }

            bfsFunc(queue);
            if (mList.size() > 0) {
                sumList.add(mList);
            }
        }
    }

    private static PriorityQueue<Edge> getEdges() {
        PriorityQueue<Edge> pqueue = new PriorityQueue<>();
        for (int i = 0; i < sumList.size(); i++) {
            ArrayList<RowAndCol> tmpList = sumList.get(i);
            int nowIslandNum = i + 1;
            for (RowAndCol tmp : tmpList) {
                for (int d = 0; d < 4; d++) {
                    int nextRow = tmp.row + dRow[d];
                    int nextCol = tmp.col + dCol[d];

                    if (isInMap(nextRow, nextCol)) {
                        if (map[nextRow][nextCol] == 0) {
                            int bridgeLen = 0;
                            while (true) {
                                nextRow = nextRow + dRow[d];
                                nextCol = nextCol + dCol[d];
                                bridgeLen++;
                                if (!isInMap(nextRow, nextCol) || (map[nextRow][nextCol] == nowIslandNum)) {
                                    break;
                                }

                                if (map[nextRow][nextCol] != 0) {
                                    if (bridgeLen > 1) {
                                        pqueue.offer(new Edge(nowIslandNum, map[nextRow][nextCol], bridgeLen));
                                        break;
                                    }
                                    break;
                                }
                            }
                        }


                    }
                }
            }
        }
        return pqueue;
    }

    private static void mstFunc(PriorityQueue<Edge> pqueue) {
        ans = 0;
        int edgeCnt = 0;
        canConnect = false;
        parent = new int[islandNum+1];
        for (int i = 1; i <= islandNum; i++) {
            parent[i] = i;
        }

        while (!pqueue.isEmpty()) {
            Edge curEdge = pqueue.poll();
            int n1 = find(curEdge.n1);
            int n2 = find(curEdge.n2);
            if (n1 != n2) {
                parent[n2] = n1;
                ans += curEdge.w;
                edgeCnt++;
            }
            if (edgeCnt == islandNum - 1) {
                canConnect = true;
                break;
            }
        }
    }

    private static void output() {
        if (canConnect) {
            System.out.println(ans);
        } else {
            System.out.println(-1);
        }
    }

    private static boolean isInMap(int nextRow, int nextCol) {
        return nextRow >= 0 && nextCol >= 0 && nextRow < N && nextCol < M;
    }

    private static void bfsFunc(Queue<RowAndCol> queue) {
        while (!queue.isEmpty()) {
            RowAndCol nowIsland = queue.poll();
            mList.add(nowIsland);
            map[nowIsland.row][nowIsland.col] = islandNum;
            for (int d = 0; d < 4; d++) {
                int nextRow = nowIsland.row + dRow[d];
                int nextCol = nowIsland.col + dCol[d];
                if (isInMap(nextRow, nextCol)) {
                    if (!visited[nextRow][nextCol]) {
                        if (map[nextRow][nextCol] != 0) {
                            RowAndCol rowAndCol = new RowAndCol(nextRow, nextCol);
                            visited[nextRow][nextCol] = true;
                            queue.offer(rowAndCol);
                        }
                    }
                }
            }
        }
    }

    static int find(int n) {
        if (n == parent[n]) {
            return n;
        } else {
            return parent[n] = find(parent[n]);
        }
    }

    static class RowAndCol {
        int row, col;

        public RowAndCol(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }

    static class Edge implements Comparable<Edge> {
        int n1, n2, w;

        public Edge(int n1, int n2, int w) {
            this.n1 = n1;
            this.n2 = n2;
            this.w = w;
        }

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

    }

}

 

백준 1414 불우이웃돕기

https://www.acmicpc.net/problem/1414

1414번: 불우이웃돕기

 

1. 문제 분석

인접 행렬의 형태로 데이터가 들어오기 때문에 이를 MST(최소 신장 트리) 가 가능한 형태로 변형하는 것이 핵심입니다. 문자열로 주어진 랜 선의 길이를 숫자로 변형해서 랜선의 총합을 저장하고, i -> j 로 가는 에지를 생성하여 에지 리스트에 저장하면 최소 신장 트리 문제로 변형할 수 있습니다.

2. 손으로 풀기

a. 입력 데이터의 정보를 배열에 저장한다.

입력으로 주어진 문자열을 숫자로 변환해서 총합으로 저장합니다.

소문자 → '입력 문자' - 'a'  + 1.

대문자 → '입력 문자' - 'A' + 27.

 

b. 저장된 에지 리스트를 바탕으로 MST 알고리즘을 수행한다.

 

c. 정답을 계산해서 출력한다.

최소 신장 트리의 결과값이 다솜이가 최소한으로 필요한 랜선의 길이입니다. 처음 저장해둔 랜선의 총합에서 MST 의 결과값을 뺀 값을 정답으로 출력합니다.

3. 슈도코드

N: 컴퓨터(노드)의 개수
edgeList: 에지 리스트를 저장할 PriorityQueue
sum = 0: 모든 에지의 가중치의 합을 저장
canConnect: 모든 컴퓨터가 연결될 수 있는지

for(N)
    for(N)
        랜선의 길이 에지리스트를 입력받기
        sum += 에지 가중치
parent: 대표 노드 배열
parent 배열을 각 배열값을 각 인덱스로 지정.
만약 노드가 1개 이면 canConnect = true;

ans = sum;: ans 에다가 연결되는 에지의 가중치를 뺄것임.
edgeCnt = 0: 연결된 에지의 개수
edgeList 가 빌때까지
    현재 에지 cur = edgeList.poll
    n1 = find(cur.n1)
    n2 = find(cur.n2)
    if(n1 != n2)
        n1 과 n2 을 연결.
        ans -= cur.가중치
        edgeCnt++;

    만약 현재 edgeCnt == N-1
        반복문 종료

만약 canConnect
    ans 출력.
아니면
    -1 출력

4. 코드

public class BaekJun1414 {

    static int N, ans;
    static PriorityQueue<Edge> edgeList;
    static int[] parent;
    static boolean canConnect;


    public static void main(String[] args) throws IOException {
        input();
        mstFunc();
        output();
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        edgeList = new PriorityQueue<>();
        ans = 0;

        for (int i = 0; i < N; i++) {
            char[] line = br.readLine().toCharArray();
            for (int j = 0; j < N; j++) {
                int temp = line[j];
                if (temp != 48) {
                    int w = 0;
                    if (temp >= 97 && temp <= 122) {
                        w = temp - 'a' + 1;

                    } else if (temp >= 65 && temp <= 90) {
                        w = temp - 'A' + 27;
                    }
                    edgeList.offer(new Edge(i + 1, j + 1, w));
                    ans += w;
                }
            }
        }

        parent = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }
        if (N == 1) {
            canConnect = true;
        }
    }

    private static void mstFunc() {
        int edgeCnt = 0;

        while (!edgeList.isEmpty()) {
            Edge cur = edgeList.poll();
            int n1 = find(cur.n1);
            int n2 = find(cur.n2);
            if (n1 != n2) {
                parent[n2] = n1;
                ans -= cur.w;
                edgeCnt++;
            }
            if (edgeCnt == N - 1) {
                canConnect = true;
                break;
            }
        }
    }

    private static void output() {
        if (canConnect) {
            System.out.println(ans);
        } else {
            System.out.println(-1);
        }
    }

    static int find(int n) {
        if (n == parent[n]) {
            return n;
        }
        return parent[n] = find(parent[n]);
    }

    static class Edge implements Comparable<Edge> {
        int n1, n2, w;

        public Edge(int n1, int n2, int w) {
            this.n1 = n1;
            this.n2 = n2;
            this.w = w;
        }

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

}