프로그래머스 위클리 챌린지 9주차 - java

문제 설명

1. n개의 송전탑은 트리 형태로 이어져있다.

2. 무조건 트리 형태이며, 중간에 한 칸을 끊어 두 개의 네트워크로 분할한다.

3. 두 네트워크 간의 차이의 절대값의 최소값을 return하면 된다.

풀이 과정

 1. 간단한 문제이지만 효율적인 방법으로 풀기는 생각보다 힘들다.....

 2. 먼저 모든 전선을 연결시킨다.

 3. 그리고 각각의 경우에서 자신의 경우 / 자식의 경우를 나누어, DFS를 해 준다.

 4. 모든 경우를 구하면서 연결을 끊은 경우를 구했으면, 그 연결을 해제하고, 다른 곳에서는 해당 연결을 다시 구하지 않을 것이다.

 5. 그 경우들에 대해 최소의 절대값을 구하면 답을 return할 수 있다.

코드