[PGM]섬 연결하기

티어 : Lv. 3
정답여부 : 오답

💡문제

● 섬 연결하기

 

💡입출력 예

💡문제 분석 요약 

• n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용

 

💡알고리즘 설계

1. 비용을 기준으로 오름차순해준다.
2. 각 자기 자신을 부모로 초기화
3. 하나의 루트 노드를 다른 하나의 루트 노드의 자식 노드로 넣어 두 트리를 합침
4. 주어진 원소의 루트 노드 번호를 반환함

 

💡시간복잡도

• O(ElogV)

 

💡코드

import java.util.Arrays;
import java.util.Comparator;

class Solution {
	static int[] island;
    
    public static int unionFind(int i){
        if(island[i] == i)
            return i;
        else
            return unionFind(island[i]); //부모노드 
    }
	
	public static int solution(int n, int[][] costs) {
		
        int answer = 0;
        island = new int[n];
        
        Arrays.sort(costs, new Comparator<int[]>(){
           public int compare(int[] o1, int[] o2){
               return o1[2] - o2[2];
           } 
        });
        
        for(int i = 0; i < n; i ++) {
        	 island[i] = i;
        }
           
        
        for(int[] item : costs){
            int a = unionFind(item[0]);
            int b = unionFind(item[1]);
            
            if(a != b){
                answer += item[2];
                island[a] = b;
            }
        
        }
        
        
		return answer;
	}
}

 

💡 틀린 이유

최소 신장 트리 Minimuim Spanning Tree 중 크루스칼 알고리즘을 이용하는 문제

그 알고리즘에 대해 공부헤봐야 된다고 생각했고 Prim 을 이용한 코드도 있어서 가져왔다.

💡 틀린 부분 수정 or 다른 풀이

import java.util.*;

class Solution {
    public class Point implements Comparable<Point>{
        int node, cost;
        
        public Point (int node, int cost) {
            this.node = node;
            this.cost = cost;
        }
        
        @Override
        public int compareTo (Point o) {
            return this.cost - o.cost;
        }
    }
    
    public List<List<Point>> map = new ArrayList<>();
    
    public int solution(int n, int[][] costs) {
        //초기화 
        for (int i = 0; i < n; i++)
            map.add(new ArrayList<>());
        for (int i = 0; i < costs.length; i++) {
            int from = costs[i][0];
            int to = costs[i][1];
            int val = costs[i][2];
            map.get(from).add(new Point(to, val));
            map.get(to).add(new Point(from, val));
        }
        
        //프림 알고리즘 
        boolean[] visit = new boolean[n];
        PriorityQueue<Point> q = new PriorityQueue<>();
        q.add(new Point(0, 0));
        
        int result = 0;
        while(!q.isEmpty()) {
            Point cur = q.poll();
            
            if (visit[cur.node]) continue;
            visit[cur.node] = true;
            result += cur.cost;
            
            for (int i = 0; i < map.get(cur.node).size(); i++) {
                int next = map.get(cur.node).get(i).node;
                int cost = map.get(cur.node).get(i).cost;
                if (visit[next]) continue;
                q.add(new Point(next, cost));
            }
        }
        
        return result;
    }
}

 

💡 느낀점

Minimuim Spanning Tree 공부와 서로소 집합에 대해 알아야 됨.

해당 개념이 없으면 섬 연결 문제는 풀이가 힘들다.

https://steady-life.tistory.com/128

https://maetdori.tistory.com/entry/프로그래머스-섬-연결하기