📚 문제 설명
n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.
송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.
🔎 입출력 예
💻 코드
import java.util.*;
import java.math.*;
class Solution {
public ArrayList<Integer>[] graph;
public int min;
public int solution(int n, int[][] wires) {
graph = new ArrayList[n+1]; // 인접 노드 리스트 저장한 배열
min = Integer.MAX_VALUE; // 트리 최소 크기
// 1. 그래프 초기화
for(int i=1; i<=n; i++) {
graph[i] = new ArrayList<Integer>();
}
// 2. 양방향 간선 추가
for(int i=0; i<n-1; i++) {
int v1 = wires[i][0];
int v2 = wires[i][1];
graph[v1].add(v2);
graph[v2].add(v1);
}
// 3. 입력된 간선을 하나씩 제거하면서 그래프를 두개의 그룹으로 분리
for(int i=0; i<n-1; i++) {
int v1 = wires[i][0];
int v2 = wires[i][1];
boolean visited[] = new boolean[n+1];
// 해당 간선을 그래프에서 제거
graph[v1].remove(Integer.valueOf(v2));
graph[v2].remove(Integer.valueOf(v1));
// dfs 함수 호출
int count = dfs(1, visited);
// 각 그룹의 노드 차이 계산
int diff = Math.abs(count - (n - count));
min = Math.min(min, diff);
// 제거한 간선 다시 graph에 추가
graph[v1].add(v2);
graph[v2].add(v1);
}
return min;
}
// 4. dfs 함수
public int dfs(int v, boolean[] visited) {
// 현재 노드 v 방문처리
visited[v] = true;
// 노드 개수 변수 count 1로 초기화
int count = 1;
for(int next : graph[v]) {
if(!visited[next]) { // 방문하지 않은 곳이라면
count += dfs(next, visited); // 방문하면서 cnt 업데이트
}
}
return count;
}
}📖 Solution
노드, 간선 그래프 문제를 처음 접해 어떻게 문제를 해결해야 할지 몰라 처음에는 HashMap을 사용해서 각 노드마다 연결된 간선의 개수를 구한 후 공식으로 풀어야 하는 줄 알았다.
하지만 힌트들을 보면서 다른 방법으로 풀어야 하는걸 인지했다.
완전 탐색 문제로 DFS 알고리즘을 활용하여 해결했다.
-
그래프 초기화
graph는 노드 개수 n에 대한 인접 리스트를 저장하기 위한 배열이다
min은 트리 최소 크기를 나타낸다. -
양방향 간선 추가
wires 배열을 순회하면서 간선 정보를 graph 배열에 추가한다
양방향이므로 add를 두번한다! -
입력된 간선을 하나씩 제거하면서 그래프를 두개의 그룹으로 분리
visited 배열은 방문 여부를 나타내는 배열이다.
dfs 함수를 재귀호출하여 시작점에서 부터 각 그룹의 노드 개수를 계산한다.
그룹의 노드 개수를 구하면 diff 차이도 구할 수 있다.
그 차이를 가지고 min을 갱신한다.
마지막으로 제거한 단선은 다시 graph에 추가하고 반복한다. -
dfs 함수
현재 노드 v를 방문처리하고 노드개수 변수인 count를 1로 초기화한다.
graph[v]에 저장된 노드를 순회하면서 방문하지 않은 노드를 탐색한다.
방문하지 않은 곳인 인접 노드 next를 재귀적으로 방문하면서 count를 업데이트해준다.
