탐욕법 05 - 섬 연결하기, 프로그래머스, 알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, 풀이과정, Leetcode, 릿코드, 코딩테스트, Tech interview, search, greedy

 

최소신장트리 (Minimum Spanning Tree, MST) 문제였는데,

 

처음보는거라서 Kruskal, Prim 방식 2가지가 있다고 해서 2가지로 풀어두었다.

 

import java.util.*;


// Kruskal mst

// Process

// 1. Input n, costs

// 2. Sort using cost (ascending way)

// 3. Iterate costs

//  3.1. Check edge is valid or not

//   3.1.1. If valid -> add cost to totalCost

//   3.1.2. If not -> next

// 4. Return totalCost



class Solution {

    public int solution(int n, int[][] costs) {

        int totalCost = 0;

        List<Integer> connected = new LinkedList<>();

        int[] disjointSet = new int[n];

        

        for (int i = 0; i < disjointSet.length; ++i) {

            disjointSet[i] = i;

        }

        

        // 2. Sort

        for (int i = 0; i < costs.length-1; ++i) {

            for (int j = i+1; j < costs.length; ++j) {

                if (costs[i][2] > costs[j][2]) {

                    int[] temp = new int[3];

                    temp[0] = costs[i][0];

                    temp[1] = costs[i][1];

                    temp[2] = costs[i][2];

                    costs[i] = costs[j];

                    costs[j] = temp;

                }

            }

        }

        

        // 3.

        int start;

        int end;

        int cost;

        for (int i = 0; i < costs.length; ++i) {

            start = costs[i][0];

            end = costs[i][1];

            if (disjointSet[start] != disjointSet[end]) {

                if (disjointSet[start] > disjointSet[end])

                    disjointSet[start] = disjointSet[end];

                else

                    disjointSet[end] = disjointSet[start];

                totalCost += costs[i][2];

                connected.add(end);

            }

            if (connected.size() == n)

                return totalCost;

        }



        return totalCost;

    }

}


// Process

// 1. Input n, costs

// 2. Make costs list for easy access

// 3. Iterate while making mst is not done

//  3.1. In vertexes in mst list, find smallest weight edge

//  3.2. Check if it's making cycle (if it's valid) **

//   3.2.1. If valid -> add to mst list, and add weight

//   3.2.2. If not -> remove that weight edge

// 4. Return weight

// // Prim mst 01

// class Solution {

//     public int solution(int n, int[][] costs) {

//         int totalCost = 0;

        

//         int[][] islands = new int[n][n];

//         List<Integer> connected = new LinkedList<>();

        

//         // Make islands plate

//         for (int i = 0; i < costs.length; ++i) {

//             islands[costs[i][0]][costs[i][1]] = costs[i][2];

//             islands[costs[i][1]][costs[i][0]] = costs[i][2];

//         }

        

//         connected.add(costs[0][0]);

        

//         while (connected.size() != n) {

//             int minCost = Integer.MAX_VALUE;

//             int minIndex = -1;

//             for (int i = 0; i < connected.size(); ++i) {

//                 int connectedIndex = connected.get(i);

//                 for (int j = 0; j < n; ++j) {

//                     if (islands[connectedIndex][j] != 0 && islands[connectedIndex][j] < minCost && !connected.contains(j)) {

//                         minCost = islands[connectedIndex][j];

//                         minIndex = j;

//                     }

//                 }

//             }

//             connected.add(minIndex);

//             totalCost += minCost;

//         }

        

//         return totalCost;

//     }

// }




// // Prim mst 02

// class Solution {

//     public int solution(int n, int[][] costs) {

//         int totalCost = 0;

//         List<Integer> connected = new LinkedList<>();

//         int[][] costPlate = new int[n][n];

        

//         for (int i = 0; i < costs.length; ++i) {

//             costPlate[costs[i][0]][costs[i][1]] = costs[i][2];

//             costPlate[costs[i][1]][costs[i][0]] = costs[i][2];

//         }

        

//         connected.add(costs[0][0]);

        

//         while (connected.size() != n) {

//             int minCost = Integer.MAX_VALUE;

//             int dstIsland = -1;

//             for (int i = 0; i < connected.size(); ++i) {

//                 int connectedIndex = connected.get(i);

//                 for (int j = 0; j < n; ++j) {

//                     if (costPlate[connectedIndex][j] < minCost && !connected.contains(j) && costPlate[connectedIndex][j] != 0) {

//                         minCost = costPlate[connectedIndex][j];

//                         dstIsland = j;

//                     }

//                 }

//             }

//             connected.add(dstIsland);

//             totalCost += minCost;

//         }

        

//         return totalCost;

//     }

// }

 

2021.03.21 - [Algorithm/Programmers] - 탐욕법 04 - 구명보트, 프로그래머스, 알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, 풀이과정, Leetcode, 릿코드, 코딩테스트, Tech interview, search, greedy

탐욕법 04 - 구명보트, 프로그래머스, 알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, 풀

2019.12.19 - [Algorithm/Leet Code] - LeetCode #706 DesignHashMap. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,그래프,Graph,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접, 데이터베이..

LeetCode #706 DesignHashMap. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,그래

2019.07.03 - [Computer/Windows] - How to check mainboard serialnumber, information. 컴퓨터 보드 시리얼넘버 정보 확인하는 방법 (Windows)

How to check mainboard serialnumber, information. 컴퓨터 보드 시리얼넘버 정보 확인하는 방법 (Windows)