전력망을 둘로 나누기

전력망을 둘로 나누기

🙋‍♂️ 들어가며

이번 문제는 조심히 봐야할게 2가지다.

• 전선 1개를 연결하지 않고 네트워크 2개로 분할하려고 한단다. 그러면 전선 1개를 끊기 위해 wires마다 각 반복문을 통해 i != j 라면 continue를 해줘야겠다

• 전선을 1개씩 연결하지 않는 상태에서 완전탐색을 진행해볼까?

그렇다면 필요한 것은

각 반복마다 graph, bfs

시간복잡도의 경우 다음과 같겠다

• 정점의 개수 : n 개
• 간선의 개수 : n-1 개

간선 하나마다 n개의 정점에 대한 bfs의 반복

즉 -> O( (n-1)*(n+n-1) )

✅ 정답 코드

// graph
import java.util.List;
import java.util.ArrayList;

// bfs
import java.util.LinkedList;
import java.util.Queue;


class Solution {
    static int min_abs = Integer.MAX_VALUE;
    
    
    public int solution(int n, int[][] wires) {
        
        // 1. 각 wire마다 끊으며 생성
        int m = wires.length;
        for (int i = 0; i < m; i++) {
            
            // 1-1. graph 생성
            List<Integer>[] graph = new ArrayList[n+1];
            for (int j = 1; j < n+1; j++) {
                graph[j] = new ArrayList<>();
            }
            
            // 1-2. 연결
            for (int j = 0; j < m; j++) {
                // 1-3. 선 1개씩 끊고 봐야하니까 (i != j)
                if (i == j) continue;
                
                // 1-4. 그 이외
                int cur_node = wires[j][0];
                int cur_to = wires[j][1];
                
                // 1-5. 전선연결은 무방향 -> 즉 양방향
                graph[cur_node].add(cur_to);
                graph[cur_to].add(cur_node);
            }
            
            // 2. bfs
            boolean[] visited = new boolean[n+1];
            int start_node = 1;
            int cnt = bfs(start_node, graph, visited);
            int diff = Math.abs(cnt - (n - cnt));
            min_abs = Math.min(diff, min_abs);
        }
        return min_abs;
    }
    
    
    
    // 3. bfs 함수
    static int bfs(int start_node, List<Integer>[] graph, boolean[] visited) {
        int cnt = 1;
        
        // 3-1. q 생성
        Queue<Integer> q = new LinkedList<>();
        q.add(start_node);
        visited[start_node] = true;
        
        // 3-2. 탐색
        while (!q.isEmpty()) {
            int cur_node = q.poll();
            
            // 3-3. next_node
            for (int next_node : graph[cur_node]) {
                // 3-4. next_node 방문 -> skip
                if (visited[next_node]) continue;
                
                // 3-5. 미방문시
                visited[next_node] = true;
                cnt++;
                q.offer(next_node);
            }
        }
        return cnt;
    }
    
}