<프로그래머스> 섬 연결하기

<링크>

 

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

 

 

<문제>

• n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.
• 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

<제한사항>

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

<입력 및 출력>

 

<아이디어>

1. 문제에서 최소 비용이라고 했으니.. MST를 생각해보자

2. MST를 쓰려면 Edge라는 class를 만들어서, from, to, weight를 각각 생성해야겠지?

3. 생성한다음.. 이제 Edge라는 걸 List에 담아서, 계속 하나씩 Edge라는 객체를 만들어서 담아주시고...

4. 정렬해서 크루스칼 돌립시당. (간적크, 간만프) ㅎ 난 크루스칼할래...

5. 대신..!!! 정렬해서 가져와야해요? 안그럼 엉망으로 들어가있어서 슬퍼짐.. (나도 알고싶지 않았어..)

6. unionfind, findSet해서 최소비용구하기!

 

<풀이 - Java >

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    
    public static class Edge {
		int from, to;
		int weight;

		public Edge(int from, int to, int weight) {
			super();
			this.from = from;
			this.to = to;
			this.weight = weight;
		}

		@Override
		public String toString() {
			return "Edge [from=" + from + ", to=" + to + ", weight=" + weight + "]";
		}

	}

	public static Edge[] edges;
	public static Map<Integer, Integer> roots;

	public int solution(int n, int[][] costs) {
		int k = costs.length;
		edges = new Edge[k];
		roots = new HashMap<>();

		for (int i = 0; i < n; i++)
			roots.put(i, i);

		for (int i = 0; i < k; i++)
			edges[i] = new Edge(costs[i][0], costs[i][1], costs[i][2]);

		Arrays.sort(edges, (o1, o2) -> o1.weight - o2.weight);

        	// 크루스칼
		int cnt = 0;
		int totalCost = 0;
		for (int i = 0; i < costs.length; i++) {

			if (unionFind(edges[i].from, edges[i].to)) {
				totalCost += edges[i].weight;
				cnt++;
			}

			if (cnt == n - 1){
				break;
                }
		}

		return totalCost;
	}

    	// 루트 경로찾기
	public static int findSet(int v) {

		if (v == roots.get(v)){
			return v;
            }

		roots.put(v, findSet(roots.get(v)));
		return roots.get(v);
	}

   	 // 유니온 파인드
	public static boolean unionFind(int a, int b) {
		int A = findSet(a);
		int B = findSet(b);

		if (A == B){
			return false;
            }

		roots.put(B, A);

		return true;
	}
}