[Lv3] 섬 연결하기

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

 

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의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

n	costs	return
4	[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]	4

 

입출력 예 설명

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

 

---

 

모든 섬을 연결하되, 최저의 비용을 목표로 합니다.

 

섬을 순서대로 지날 필요도 없고, 한 섬에서 지을 수 있는 다리의 수는 없을 수도, 아주 많을 수도 있습니다.

 

2-0-1 다리를 지었다면, 2-1은 지으면 안됩니다.

 

 

우선 최저의 비용이 목표이니, 우선순위가 높은 목표로 판단하여, 배열들을 가격순으로 정렬합니다.

Comparator<int[]> c1 = (a,b)->{
    return a[2]-b[2];
};
Arrays.sort(costs,c1);

 

주어진 건설가능 한 다리들을 탐색하면서 지나기 위해, 다리 건설 여부를 측정하고,

섬의 가능 여부를 측정할겁니다. (2-0-1을 지었으면 2-1을 안짓도록)

boolean[] check = new boolean[costs.length];
boolean[] ok = new boolean[n];
ok[costs[0][0]] = true;
ok[costs[0][1]] = true;
check[0] = true;
int answer = costs[0][2];
int complete = 2;

다리 건설 여부 check[]와 섬의 가능 여부 ok[]로 둡니다.

 

가장 가격이 저렴한 0번 부터 건설한 채로 시작할겁니다.

 

0번째에 해당하는 섬들을 방문 가능 섬으로 표시하고, 0번째 다리도 건설 상태로,

 

가격인 answer는 첫번째 다리의 가격을 지불한 상태로, 총 섬의 수 complete는 2로 합니다.

 

complete가 섬의 수에 도달하면 모든 섬이 방문 가능한 상태로 나타내도록 코드를 짤겁니다.

 

while(complete<n) {
    for(int i=1;i<check.length;i++) {
        if(!check[i] && ((ok[costs[i][0]]&&!ok[costs[i][1]])||(ok[costs[i][1]]&&!ok[costs[i][0]]))) {
            check[i] = true;
            ok[costs[i][0]] = true;
            ok[costs[i][1]] = true;
            complete++;
            answer+=costs[i][2];
            break;
        }
    }
}
return answer;

0번째 다음인 1번째부터 탐색을 시작합니다.

 

해당 다리가 아직 건설 전(!check[i])이고,

다리 양 끝 섬 한 군데만 방문 가능 상태일 때 건설하게 할 것입니다.

(양쪽 다 불가면 아예 못짓는거고, 둘 다 가능이면 지을 필요가 없고.)

 

배열은 저렴한 순으로 이미 정렬되어 있습니다.

 

다리가 건설되면 break로 다시 처음부터 탐색하게 할겁니다.

 

배열을 탐색하면서 양쪽 끝이 둘 다 방문 불가능해서 그 때는 짓지 않았지만,

새롭게 정보가 바뀌면서 이젠 다시 건설 가능해진 저렴한 다리를 우선적으로 하기 위해서입니다.

 

이렇게 저렴하면서 건설 가능한 다리만 순서대로 건설하고, complete가 섬의 수에 도달하면 이 때의 가격을 반환하면 됩니다.