섬 연결하기(프로그래머스-탐욕법)

문제

코드

import java.util.*;
class Solution {
    public int solution(int n, int[][] costs) {
        int answer = 0;
        List<int[]> arr=new ArrayList<>();
        List<Integer> visited=new ArrayList<>();

        for(int[] a:costs)
            arr.add(a);
        Collections.sort(arr,(a,b)->a[2]-b[2]);
        
        visited.add(arr.get(0)[0]);
        visited.add(arr.get(0)[1]);
        answer+=arr.get(0)[2];
        arr.remove(0);
        while(visited.size()<n){
            for(int i=0;i<arr.size();i++){
                if(visited.contains(arr.get(i)[0])||visited.contains(arr.get(i)[1])){
                    if(visited.contains(arr.get(i)[0])&&visited.contains(arr.get(i)[1])) continue;
                    if(!visited.contains(arr.get(i)[0])) visited.add(arr.get(i)[0]);
                    if(!visited.contains(arr.get(i)[1])) visited.add(arr.get(i)[1]);
                    answer+=arr.get(i)[2];
                    arr.remove(i);
                    break;
                }
            }
        }
        
        return answer;
    }
}

풀이

크루스칼 알고리즘으로 해결하였다.
(1) 먼저, 간선을 새로 저장할 ArrayList(arr)을 만들고, 비용이 적은 순서대로 정렬한다.
(2) 크루스칼 알고리즘을 실행한다.

• 크루스칼 알고리즘을 시작하기 전에 먼저, 가장 비용이 적게드는 간선 하나를 선택하고, visited에 연결된 섬의 번호를 넣어준다. 선택했던 간선은 arr에서 제거해 준다.
• visited의 크기가 n이 될 때 까지(모든 섬을 방문할 떄 까지) 크루스칼 알고리즘을 실행한다.
• 남은 간선 중 가장 비용이 작은 간선을 확인한다. 이 때, 지금까지 방문했던 섬과 연결할 수 있는 간선이어야 한다. 그리고, 간선을 연결했을 때 싸이클이 생기면 안된다. 연결할 수 있는 간선이면 visited에 방문한 섬의 번호를 넣어주고, answer에 비용도 더해준 후, arr에서 간선을 제거한다.

(3) 위처럼 크루스칼 알고리즘을 진행하다가, 모든 섬을 방문했을 때 종료하고 answer을 반환한다.

결과

이 문제를 보자마자, 이거 분명 예전에 학교에서 알고리즘 강의를 들었을 때 배웠던 것 같은데 라는 생각이 들었다.
그리고 정확히 어떤 알고리즘이었는지는 기억이 안나지만, 기억을 되살려 보면서 풀었다.
가장 작은 간선만 선택하는 방법이 기억에 났다.
모든 섬을 방문할 떄 까지, 연결할 수 있는 간선을 비용이 작은 순서대로 선택해 주었는데 오답이 났다.
왜 그런가 했더니, 싸이클이 생기는 경우까지 선택해버린 것이다.
선택한 간선의 섬 두개가 이미 방문한 섬일 때는 선택하지 않으면 싸이클이 생기지 않는다.
문제를 풀고 나서 이 문제를 검색해봤는데, 크루스칼 알고리즘이라고 한다.
기억이 났다. 그땐 책으로만 공부했었는데 이렇게 쓰일 줄 몰랐다. 이게 그리디였구나.

출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges