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

문제 출처: programmers.co.kr/learn/courses/30/lessons/42861

코딩테스트 연습 - 섬 연결하기

풀이

각각 섬끼리 연결된 간선의 개수를 구할 수 있고 가중치가 존재하므로 크루스칼 알고리즘을 사용하면 쉽게 풀수있다.

1. 우선 섬끼리 연결된 정보와 가중치를 저장할 객체 클래스를 만든다.

2. 각 섬들이 연결되고 최종적으로 부모?섬이 어디인지 인덱스를 가지고 있는 parents 배열을 생성한다.

3. 처음에는 각 섬들은 스스로를 부모로하도록 parents 배열을 초기화 한다.

4. 가중치가 낮은 것부터 탐색해야 최선의 값(최소값)을 구할 수 있기 때문에 일단 가중치를 기준으로 Sort를 해준다.

5. 각자 섬들을 탐색하여 간선을 연결해주면서 가중치를 더해준다.

 

코드

	import java.util.*;
	//크루스칼
	class Solution {
	static class Edge implements Comparable<Edge>{
	int from, to, weight;
	Edge(int from,int to,int weight){
	this.from=from;
	this.to=to;
	this.weight=weight;
	}
	@Override
	public int compareTo(Edge o){
	return Integer.compare(this.weight, o.weight);
	}
	}
	static Edge[] edgeList;
	static int[] parents;
	public int solution(int n, int[][] costs) {
	int answer = 0;
	parents = new int[n];
	int e = costs.length;
	edgeList = new Edge[e];
	for(int i=0;i<costs.length;i++){
	int from=costs[i][0];
	int to = costs[i][1];
	int weight = costs[i][2];
	edgeList[i] = new Edge(from,to,weight);
	}
	//정렬한다.
	Arrays.sort(edgeList);
	//각 정점은 자기를 부모로 가지게 초기화한다.
	make(n);
	int cnt=0;
	for(Edge edge : edgeList){
	if(union(edge.from,edge.to)){
	cnt++;
	answer+=edge.weight;
	if(cnt==n-1){
	break;
	}
	}
	}
	return answer;
	}
	void make(int Edge){
	for(int i=0;i<Edge;i++){
	parents[i]=i;
	}
	}
	boolean union(int x,int y){
	int xRoot = find(x);
	int yRoot=find(y);
	if(xRoot==yRoot){
	return false;
	}
	parents[yRoot]=xRoot;
	return true;
	}
	int find(int a){
	if(a==parents[a])
	return a;
	else{
	return parents[a]=find(parents[a]);
	}
	}
	}

view raw 섬연결하기 hosted with ❤ by GitHub