프로그래머스 - 섬연결

섬연결 (2021. 07. 30) Connect Island

문제 및 풀이 주소

Programmers
Git Solution

문제 설명

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

문제 해결

해당 문제는 주제인 탐욕법을 포함해서 또한가지의 알고리즘이 필요했다.(엄청난 삽질 또해버린..) 필요한 알고리즘은 다음과 같다.

크루스칼 알고리즘

• 그래프 내의 모든 정점을 포함하고 사이클이 없는 연결 선을 그렸을 때, 가중치의 합이 최소가 되는 상황을 구하고 싶을 때 사용
• 최소 신장 트리를 구하기 위한 알고리즘
• 실제 크루스칼 알고리즘은 배열 초기값을 해당 노드의 값으로 하였는데 그부분을 안보고 구현하다보니 초기값을 -1로 지정

---

크루스칼 알고리즘 구현 방식

• 배열의 시작값과, 종료값에 대한 탐색(DFS)으로 최종 부모값을 찾는다.
• 구해진 시작값에 대한 부모값과, 종료값에 대한 부모값을 비교한다.
  • 비교값이 큰값이 방문배열의 인덱스 값이되고, 작은 값이 해당 방문배열의 값이 된다.
• 시작값에 대한 부모값과, 종료값에 대한 부모값이 같은 경우, 만들어지면 안되는 사이클의 형태가 되므로 (A->B<->C) 아무런 행위를 하지 않는다.

이슈케이스 및 해결 방안 추측

초기에는 크루스칼 알고리즘을 사용하지 않고 내가 정의한 조건들을 지속적으로 추가해서 구하는 방식으로 하였다.(틀린방식이라고는 할 수 없지만 조건이 점점 산으로 간다.) 사이클이 만들어지지 않기위한 방식을 각각의 시작값 배열과 종료값 배열로 나누어서 처리하고, 그것에 대해서 상황별 사이클이 만들어지는 조건값을 추가하였는데, 엄청난 테스트 케이스를 추가하고 조건에 성립함에도 불구하고 실제 테스트 케이스에서 실패를 하니, 각각의 조건이 상황에 따라 다르게 있는것이 있어 해당 방식은 불가능한것을 깨달았다.

이슈 케이스

문제 해결

크루스칼 알고리즘을 사용하였다.

최상위 부모노드를 찾기 위한 코드는 다음과 같다

// 재귀함수를 사용하여 -1값이 나올때까지
private int findRoot(int child, int[] visitArr) {
    if(child == visitArr[child]){
        return child;
    }else if (visitArr[child] == -1) {
        return child; // 기존 부모값 사용
    } else {
        return findRoot(visitArr[child], visitArr);
    }
}

방문배열에 값을 설정하기 위한 조건은 다음과 같다

// 순서가 상관없으므로 두 root값을 모두 비교해야한다.
// 큰값이 방문배열 Index, 작은값이 방문배열 Value
if(startRoot > endRoot){
    visitArr[startRoot] = endRoot;
}else{
    visitArr[endRoot] = startRoot;
}
// 양쪽 부모가 같지 않으므로 연결이 가능하므로 연산한다.
answer += cost[2];

테스트 결과

테스트 번호	통과여부	메모리 및 시간	테스트 번호	통과여부	메모리 및 시간
테스트 1	통과	(11.49ms, 53.5MB)	테스트 5	통과	(6.98ms, 52.8MB)
테스트 2	통과	(4.35ms, 52.3MB)	테스트 6	통과	(6.56ms, 52.4MB)
테스트 3	통과	(4.39ms, 53.3MB)	테스트 7	통과	(12.55ms, 52.1MB)
테스트 4	통과	(9.10ms, 53.3MB)	테스트 8	통과	(6.82ms, 52.1MB)

후기

해당 문제는 분명 정해진 알고리즘(쿠르스칼)을 사용하지 않고 조건을 잘 설정하기만 해도 가능할 것으로 보인다. 문제에 해당하는 조건을 생각해 보았지만 구멍이 계속 존재하였고 원하는 결과가 나오지 않았다..