코딩테스트 연습 > 전력망을 둘로 나누기 (완탐, BFS)

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

 

 

풀이 - 나의 생각

 

선분을 하나씩 제거하면서 BFS로 방문 후 나눠진 전력망의 크기를 비교했습니다.

 

 

코드

 

import java.util.*;

class Solution {
    static List<Integer>[] list;
    static boolean[] visited;
    
    public int solution(int n, int[][] wires) {
        int start = 0, end = 0, A = 0, B = 0, diff = 0, min = Integer.MAX_VALUE;
        list = new ArrayList[n+1];
        
        for(int i = 0; i <= n; i++){
            list[i] = new ArrayList<>();
        }
        
        for(int i = 0; i < wires.length; i++){
            start = wires[i][0];
            end = wires[i][1];    
            list[start].add(end);
            list[end].add(start);
        }
        
        for(int i = 0; i <  wires.length; i++){
            start = wires[i][0];
            end = wires[i][1];
            visited = new boolean[n+1];
            
            A = check(start, end);
            B = n - A;
            diff = Math.abs(B - A);
            if(diff == 0) return 0;
            min = Math.min(min, diff);
        }
        
        
        return min;
    }
    
    public int check(int start, int exclude){
        int cnt = 0;        
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(start);
        visited[start] = true;
        
        while(!q.isEmpty()){
            int now = q.poll();
            cnt++;
            for(Integer next : list[now]){
                if(visited[next] || exclude == next) continue;
                visited[next] = true;
                q.offer(next);
            }
        }
        
        return cnt;
    }
}

 

 

 

 

 

 

 

다음에 또 봐요