오늘은 아침에 코테를 보고, 학교에 가서 개별 연구 미팅을 하고, 과제까지 제출하고 나니 이미 밤 12시였고ㅠㅡㅠ,, 오늘 컨디션 너무 안 좋아서 머리가 핑 돌고,, 쓰러질 거 같고,, 토 할 거 같고,, 밥도 잘 못 챙겨먹고,, 할 건 많이 남았고,, 정말 울고 싶던 하루였지만,, 😭😭😭😭😭 ( 찡찡,, )
집에 와서 밥 챙겨묵고 ~ 누워서 좀 쉬니까 살만해서 꾸역꾸역 일어나 문제를 풀었다,, 장하다 나 ! 아침에 코테 봤으니까 오늘 세 문제나 푼 고 아냐 ~? 라고 핑계를 대보려다가 이겨냈다 ! 정말 기특해 나 !
그래서 오늘 푼 문제는 뭐냐면 ! 프로그래머스 고득점 kit 그리디 분류의 level3 문제였다 !
https://programmers.co.kr/learn/courses/30/lessons/42861
( 크크 이제 분류별로 한 문제씩만 남았다 ! 다음주 안에 다 뿌시고 ! 백준 문제 모음집을 풀어야지 ! )
문제 설명
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 |
풀이 방법
먼저 최소의 cost로 모든 섬을 연결해야 하니까 cost가 낮은 다리 순서로 체크하며 다리를 건설해 나가야 한다 !
그래서 먼저 cost를 기준으로 정렬을 한 후, 가장 낮은 cost의 다리는 우선 건설을 한다. 다리를 건설할 때, 도달할 수 있는 섬 리스트에 섬을 추가해주고, 비용 역시 더해준다.
첫 번째 다리를 건설한 후에는 그 다음 비용이 작은 순서부터 탐색하며, 현재 체크하고 있는 다리의 양 쪽 섬과 도달할 수 있는 섬 리스트를 비교한다. 경우의 수는 아래의 세 개이다.
- 현재 체크하는 다리의 양 쪽 섬 모두 도달할 수 있는 섬 목록에 없는 경우
- 현재 체크하는 다리의 한 쪽 섬만 도달할 수 있는 섬 목록에 있는 경우
- 현재 체크하는 다리의 양 쪽 섬 모두 도달할 수 있는 섬 목록에 있는 경우
1번 경우
1번의 경우는 우선 다리를 짓지 않고, 다음 다리를 체크하러 넘어간다. 그 이유는 아래의 그림처럼 모든 섬에 다리가 지어졌지만 연결되지 않는 경우가 발생할 수 있기 때문이다.
하지만 추후에 연결되는 다리에 의해 연결될 수 있고, 비용이 낮은 다리이므로 나중에 다시 탐색할 여지를 남겨둔다 !
2번 경우
이 경우에는 이미 도달할 수 있는 섬에서 새로운 섬으로 연결되는 다리이므로 다리를 건설한다. 다리를 건설할 때에는 도달할 수 있는 섬 리스트에 새로운 섬을 추가해주고, 총 건설 비용에 cost를 더해준다. 그리고 다리 건설 리스트에서 제거해준다 !
3번 경우
이 경우는 이미 다 도달할 수 있는 섬들이므로, 그리고 이미 더 적은 비용으로 지어진 것이므로 지을 필요가 없다. 그러므로 다리를 짓지 않고 그냥 다리 건설 리스트에서 제거해준다 !
위의 과정을 도달할 수 있는 섬에 모든 섬이 들어올 때까지 반복하여주면 된다 ! 1번 경우처럼 후에 다시 건설하게 될 다리가 있을 수 있으므로, 지은 다리나 지을 필요가 없는 다리는 제거해주고, 다리 건설 목록 리스트는 계속해서 처음부터 탐색해준다 !
코드로 구현할 때에는 comparator interface를 이용하여 cost 순서로 정렬해주었다. 이후에 도달할 수 있는 섬 리스트를 저장할 ArrayList를 만들어주고, 첫 번째 다리는 건설하고 반복을 시작해주었다. 이 때, while로 모든 섬에 도달할 수 있는지를 체크해주고, 그 내부에서는 다리 건설 리스트를 반복해주었다. 반복하며 1, 2, 3 경우를 판단하여 건설이나 제거 등의 처리를 해주었다.
코드
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
public class Solution {
public static int solution(int n, int[][] costs) {
int answer = 0;
ArrayList<int[]> cost_arr = new ArrayList<>(Arrays.asList(costs));
cost_arr.sort(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[2] - o2[2];
}
});
ArrayList<Integer> possible = new ArrayList<>();
int[] current = cost_arr.get(0);
possible.add(current[0]);
possible.add(current[1]);
answer += current[2];
int count, new_node = 0;
while(possible.size() < n){
for(int i=1; i< cost_arr.size(); i++){
current = cost_arr.get(i);
count = 0;
if(possible.contains(current[0])){
count++;
new_node = 1;
}
if(possible.contains(current[1])){
count++;
new_node = 0;
}
if(count == 0) continue;
if(count == 1){
possible.add(current[new_node]);
answer += current[2];
}
cost_arr.remove(i);
break;
}
}
return answer;
}
}코드를 보면서 설명을 읽으면 쉽게 이해할 수 있을 것이다 ! 나는 이미 고민을 거쳐 구현까지 해본 상태라서 처음 보는 사람이 이해하기 좋게 글을 쓰고 있는지 판단하기가 쉽지 않다.. 흠 블로그 잘 쓰기란 어렵다 ! 구현에서 이해가 가지 않는 부분이나 개선하면 좋을 부분이 보인다면 댓글 남겨주세용 ! 🙂
( 아우.. 허리아파.. 여러분 허리 다들 안녕하신가요.. 요즘 허리가 너무 아파요.. 다들 건강하게 개발합시다..ㅠㅡㅠ )
