[알고리즘] 프로그래머스 - 섬 연결하기(탐욕법)

1. 문제

2. 문제 풀이

1. 각각의 섬이 다리로 연결된 비용을 map 배열에 저장한다.

2. 시작 섬으로 0번째 섬을 방문 했다고 표시해준다.

3. 모든 섬을 방문 하지 않았다면 모든 섬을 방문할 때 까지 최소값을 구한다.

4. 현재 방문한 섬들을 기준으로 이 섬과 연결된 다리중 가장 최소값을 선택해서 다리를 newMap 배열에 건설했다고 표시한다.

5. 4번 과정을 반복해서 answer에 각각의 최소값을 더해주고, 모든 섬을 방문하면 답이 나온다.

public class Solution {

    int[][] map;
    int[][] newMap;
    boolean[] visit;
    int answer = 0;

    public boolean isAllVisit(){
        boolean flag = true;
        for(int i=0;i<visit.length;i++){
            if(visit[i] == false) {
                flag = false;
                break;
            }
        }
        return flag;
    }

    public void selectBridge(int n){
        int len = visit.length;
        int cx = 0;
        int cy = 0;
        int min = 99999999;

        for(int i=0;i<len;i++){
            for(int j=0;j<len;j++){
                if(visit[i] == true && visit[j] == false && map[i][j] <= min && map[i][j] != 0 && newMap[i][j] == 0){
                    min = map[i][j];
                    cx = i;
                    cy = j;
                }
            }
        }

        newMap[cx][cy] = min;
        visit[cy] = true;
        answer += min;
    }

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

        int len = n;
        map = new int[n][n];
        newMap = new int[n][n];
        visit = new boolean[n];

        //초기화
        for(int i=0; i<costs.length;i++){
            int s = costs[i][0];
            int e = costs[i][1];
            map[s][e] = costs[i][2];
            map[e][s] = costs[i][2];
        }

        //초기 노드 선택
        visit[0] = true;

        while(!isAllVisit()){
            selectBridge(n);
        }

        return answer;
    }

}