전력망을 둘로 나누기 접근 방법

for (int i = 0; i < wires.length; i++) { adj[wires[i][0]][wires[i][1]] = adj[wires[i][1]][wires[i][0]] = 1; // 양방향 }

// 하나씩 끊어보기 for (int i = 0; i < wires.length; i++) { int sNode = wires[i][0]; int eNode = wires[i][1]; // 연결된 송전탑 끊기 adj[sNode][eNode] = 0; adj[eNode][sNode] = 0; answer = Math.min(answer, bfs(adj, new boolean[n+1], 1, n)); /*int nodeCnt = dfs(adj, new boolean[n+1], 1); answer = Math.min(answer, (int)Math.abs(nodeCnt-(n-nodeCnt)));*/ // 연결된 송전탑 연결 adj[sNode][eNode] = 1; adj[eNode][sNode] = 1; }

public int bfs(int[][] adj, boolean[] v, int sNode, int n) { Queue<Integer> q = new LinkedList<>(); q.offer(sNode); int cnt = 1; // 개수 1 더하기(1번 송전탑) while(!q.isEmpty()) { int node = q.poll(); v[node] = true; for (int i = 1; i < v.length; i++) { if(!v[i] && adj[node][i] == 1) { q.offer(i); cnt++; } } } return (int)Math.abs(cnt - (n - cnt)); }

public int dfs(int[][] adj, boolean[] v, int sNode) { int cnt = 1; // 현재 송전탑 v[sNode] = true; for (int i = 0; i < adj.length; i++) { if(!v[i] && adj[sNode][i] == 1) { cnt += dfs(adj, v, i); } } // System.out.println(Arrays.toString(v)); // System.out.println(cnt); return cnt; }