전력망 둘로 나누기 알고리즘 (DFS, JAVA)
AI Store에서 AI코딩으로 만들어진 앱을 만나보세요!
지금 바로 방문하기

프로그래머스 - 전력망을 둘로 나누기(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)