코딩테스트/프로그래머스
[코딩테스트] Java 전력망을 둘로 나누기
[dev] hiro
2024. 11. 13. 00:39
제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.
포인트
union-find 함수를 사용하여 연결된 전선의 갯수를 구하는 문제를 사용합니다. 끊어진 전선에 대하여 완전탐색을 진행합니다.
소스코드
class Solution {
public int[] parent;
public void init(int n) {
for(int i = 1; i <= n; i++) {
parent[i] = i;
}
}
public int findParent(int n) {
if (parent[n] != n) {
parent[n] = findParent(parent[n]);
}
return parent[n];
}
public void union(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a < b) {
parent[b] = a;
} else {
parent[a] = b;
}
}
public int solution(int n, int[][] wires) {
int answer = Integer.MAX_VALUE;
int len = wires.length;
for(int i = 0; i < len; i++) {
// i는 끊는
parent = new int[n+1];
init(n);
for(int j = 0; j < len; j++) {
if(i == j) {
continue;
}
if(findParent(wires[j][0]) != findParent(wires[j][1])) {
union(wires[j][0], wires[j][1]);
}
}
// 각 송전탑의 최상위 부모 노드 갱신 및 개수 세기
Map<Integer, Integer> connect = new HashMap<>();
for (int j = 1; j <= n; j++) {
int root = findParent(j);
connect.put(root, connect.getOrDefault(root, 0) + 1);
}
// 두 개의 그룹으로 나뉘었는지 확인하고 차이 계산
if (connect.size() == 2) {
List<Integer> counts = new ArrayList<>(connect.values());
int diff = Math.abs(counts.get(0) - counts.get(1));
answer = Math.min(answer, diff);
}
}
return answer;
}
}코드 설명
- 클래스 변수
- parent: 각 노드의 부모를 나타내는 배열입니다. Union-Find에서 사용되는 핵심 배열입니다.
- init 메서드
- 부모 배열을 초기화합니다. 각 노드의 부모를 자기 자신으로 설정하여, 초기에는 모두 독립적인 집합으로 시작합니다.
- findParent 메서드
- 주어진 노드 n의 부모를 찾는 함수입니다. 경로 압축(Path Compression) 기법을 사용하여 부모를 재귀적으로 찾아, 트리의 높이를 낮추고 효율성을 높입니다.
- union 메서드
- 두 집합을 합치는 함수입니다. findParent를 이용해 각 노드의 부모를 찾고, 더 작은 부모를 선택하여 큰 부모를 그 아래로 합칩니다. 이로써 두 집합이 하나로 결합됩니다.
- solution 메서드
- 전선 끊기:
- 전선이 여러 개 있는데, 각 전선에 대해서 하나씩 끊어보고 그 결과를 확인합니다. i == j일 때는 i번째 전선만 끊고 나머지 전선은 그대로 연결합니다.
- 전선 연결:
- 각 전선의 두 끝을 union으로 연결합니다. 즉, 전선들이 연결된 노드를 하나의 네트워크로 묶습니다.
- 네트워크 크기 계산:
- 연결된 네트워크의 부모 노드(parent[j])를 기준으로 각 네트워크의 크기를 계산합니다. 부모 노드별로 네트워크에 속한 노드의 개수를 connect 맵에 저장합니다.
- 두 네트워크로 분리되었는지 확인:
- connect.size()가 2일 때, 즉 두 개의 독립적인 네트워크로 나누어진 경우에만 그 크기 차이를 계산합니다.
- counts.get(0)과 counts.get(1)을 비교하여 두 네트워크의 크기 차이를 diff로 구하고, 이 값이 최소가 되도록 answer를 갱신합니다.
- 전선 끊기: