프로그래머스 - 전력망을 둘로 나누기(JAVA)
카테고리
프로그래밍/소프트웨어 개발
서브카테고리
알고리즘
대상자
- Java 알고리즘 문제 해결자 및 그래프 탐색 기법 학습자
- 난이도: 중급 (DFS, 그래프 탐색, 최소 차이 계산 기법 이해 필요)
핵심 요약
- 문제 목적: 전력망을 끊었을 때 두 그룹의 송전탑 수 차이의 절대값 최소화
- 알고리즘: DFS를 활용한 완전 탐색으로 모든 가능성을 시도
- 핵심 구조:
Map
로 그래프 구축,> dfs
함수에서 자식 노드 수 계산 및min
값 업데이트
섹션별 세부 요약
1. 문제 정의
- 입력: 송전탑 수
n
(222 ≤ n ≤ 100100100), 전선 정보wires
(길이n-1
) - 목표: 전선 하나를 끊었을 때 두 전력망의 송전탑 수 차이의 절대값 최소화
- 특징:
wires
는 트리 구조로, 사이클이 없음
2. 그래프 구축
Map
사용: 각 노드의 연결 정보 저장> - 초기화:
```java
for (int[] wire : wires) {
map.get(wire[0]).add(wire[1]);
map.get(wire[1]).add(wire[0]);
}
```
3. DFS 구현
- 방문 여부 체크:
boolean[] visited
배열로 노드 탐색 제어 - 재귀적 탐색:
```java
int count = 1;
for (int next : nexts) {
if (!visited[next]) count += dfs(...);
}
```
min
계산:
```java
min = Math.min(min, Math.abs(n - 2 * count));
```
4. 시간 복잡도
- O(N): 트리 구조의 DFS 탐색으로 선형 시간 소요
- 완전 탐색의 효율성: 노드 수가 대규모일 때도 성능 저하 없음
결론
- 핵심 팁: 트리 구조에서 DFS를 통해 모든 가능성을 탐색하고,
min
변수로 최소 차이를 계산 - 코드 구조:
Map
을 활용한 그래프 표현,dfs
함수의 재귀적 호출 및min
업데이트 - 예제:
n=4
,wires=[[1,2],[1,3],[1,4]]
→ 최소 차이 0 (예: 2-2)