문제
풀이
1차 시도: 그래프
각 섬을 탐색해가며 그 섬에 연결된 최소비용 다리를 선택하는 방식으로 코드를 작성했다. 하지만 이 방식으로는 모든 섬이 연결된다는 보장이 없다. 그래서 테케 1번 빼고 다 오답이 떴다.
import java.util.*;
class Solution {
private boolean[] visited;
private List<Map<Integer, Integer>> graph = new ArrayList<>();
private int answer;
public int solution(int n, int[][] costs) {
visited = new boolean[n];
initGraph(costs);
findMinPath();
return answer;
}
private void initGraph(int[][] costs) {
for (int i = 0; i < visited.length; i++)
graph.add(new HashMap<>());
for (int[] cost : costs) {
graph.get(cost[0]).put(cost[1], cost[2]);
graph.get(cost[1]).put(cost[0], cost[2]);
}
}
private void findMinPath() {
for (int currentNode = 0; currentNode < visited.length; currentNode++) {
if (!visited[currentNode]) {
int minCostValue = Integer.MAX_VALUE;
int minCostNode = -1;
for (int adjacent : graph.get(currentNode).keySet()) {
int bridgeCost = graph.get(currentNode).get(adjacent);
if (bridgeCost < minCostValue) {
minCostNode = adjacent;
minCostValue = bridgeCost;
}
}
answer += minCostValue;
visited[currentNode] = true;
visited[minCostNode] = true;
}
}
}
}정답: Kruskal 알고리즘 적용
연결이 되지 않은 부분을 찾아서 연결하는 건 최고로 비효율적일 것 같아서 검색을 했더니, 크루스칼 알고리즘을 적용하는 문제였다. 크루스칼 알고리즘에 관한 내용은 여기서 확인할 수 있다.
아무튼 앞에서 내가 했던 것처럼 주어진 costs를 그래프를 만들 필요도 없었다. 크루스칼 알고리즘을 적용하면 쉽게 풀리는 문제였다.
costs배열을 비용 기준으로 오름차순으로 정렬해서- 사이클이 생성되지 않는 최소 비용 간선을 경로에 추가한다.
- 사이클 테이블이 모두 같은 부모 노드를 가리키면 최소 비용 경로가 완성된 것이다.
이러한 알고리즘을 적용한 코드는 아래와 같다.
import java.util.*;
class Solution {
private static final int COST = 2;
public int solution(int n, int[][] costs) {
Arrays.sort(costs, (Comparator.comparingInt(o -> o[COST])));
int[] parentNodes = createCycleTable(n);
int answer = 0;
for (int[] edge : costs) {
if (parentNodes[edge[0]] != parentNodes[edge[1]]) {
updateConnectedNodes(parentNodes, edge[1], edge[0]);
answer += edge[COST];
}
if (pathCreated(parentNodes)) break;
}
return answer;
}
private void updateConnectedNodes(int[] parentNodes, int from, int to) {
int target = parentNodes[from];
for (int i = 0; i < parentNodes.length; i++)
if (parentNodes[i] == target)
parentNodes[i] = parentNodes[to];
}
private boolean pathCreated(int[] parentNodes) {
for (int i = 0; i < parentNodes.length - 1; i++)
if (parentNodes[i] != parentNodes[i + 1]) return false;
return true;
}
private int[] createCycleTable(int n) {
int[] result = new int[n];
for (int i = 0; i < n; i++) result[i] = i;
return result;
}
}정답: Union-Find 알고리즘 적용
위의 코드에서는 하나의 edge를 추가할 때마다 parentNodes를 처음부터 끝까지 탐색하며 모든 parent를 업데이트했다. 이렇게 하기보다는, Union-Find 알고리즘을 적용해서 시간복잡도를 줄여 최적화하는 것이 바람직하다.
Union-Find 알고리즘에 관한 내용은 여기에 정리해놓았다. 이 내용을 적용한 코드는 아래와 같다.
import java.util.*;
class Solution {
private static final int COST = 2;
public int solution(int n, int[][] costs) {
Arrays.sort(costs, (Comparator.comparingInt(o -> o[COST])));
int[] parentNodes = createCycleTable(n);
int answer = 0;
for (int[] edge : costs) {
if (!hasSameParent(parentNodes, edge[0], edge[1])) {
union(parentNodes, edge[0], edge[1]);
answer += edge[COST];
}
if (pathCreated(parentNodes)) break;
}
return answer;
}
private int[] createCycleTable(int n) {
int[] result = new int[n];
for (int i = 0; i < n; i++) result[i] = i;
return result;
}
private boolean hasSameParent(int[] parentNodes, int a, int b) {
return findParent(parentNodes, a) == findParent(parentNodes, b);
}
private int findParent(int[] parentNodes, int node) {
if (parentNodes[node] == node) return node;
return findParent(parentNodes, parentNodes[node]);
}
private void union(int[] parentNodes, int a, int b) {
int parentA = findParent(parentNodes, a);
int parentB = findParent(parentNodes, b);
if (parentA > parentB) parentNodes[parentA] = parentB;
else parentNodes[parentB] = parentA;
}
private boolean pathCreated(int[] parentNodes) {
for (int i = 0; i < parentNodes.length - 1; i++)
if (parentNodes[i] != parentNodes[i + 1]) return false;
return true;
}
}학교에서 컴알 시간에 배운 알고리즘인데 정작 문제 풀 때는 자유자재로 적용을 하지 못 해서 아쉬웠다. 여태 배운 것들도 복습을 잘 해서 여러 상황에 적용하여 문제를 풀 수 있도록 노력해야겠다.
