[프로그래머스] LEVEL2 전력망을 둘로 나누기 - 자바

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

코딩테스트 연습 - 전력망을 둘로 나누기

 

 

[풀이 코드]

import java.util.*;

class Solution {
    static List<List<Integer>> list; 
    public int solution(int n, int[][] wires) {
        int answer = -1;
        list = new ArrayList<>();
        for(int i=0; i<n+1; i++){
            list.add(new ArrayList<>());
        }
        
        for(int i=0; i<wires.length; i++){
            list.get(wires[i][0]).add(wires[i][1]);
            list.get(wires[i][1]).add(wires[i][0]);
        }
        

        int min = Integer.MAX_VALUE; // 최댓값 설정
        for(int i=1; i<=n; i++){
            for(int num : list.get(i)){
                if(i < num) {
                    int tCnt = bfs(i, num, n); //BFS한번만!!
                    min = Math.min(min, Math.abs(tCnt - (n-tCnt))); 
                }
            }
        }
        
        return min;
    }
    
    static int bfs(int start, int end, int n){
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[n+1];
        int cnt = 1;
        q.offer(start);
        visited[start] = true;
        
        while(!q.isEmpty()){
            int v = q.poll();
            
            for(int i : list.get(v)){
                if(!visited[i] && i != end){
                    q.offer(i);
                    visited[i] = true;
                    cnt++;
                }
            }
        }
        return cnt;
    }
}

• 만약에 각 노드마다 가중치가 있다고 가정한다고 해도 BFS로 풀 수 있을지가 궁금하다. 
  
  

 

• 이때 간선이 중복되어 탐색되는 부분을 방지하기 위해 if(i < num) 조건문을 넣어줬다. 이 부분은 직접 간선 리스트를 그려보면 이해가 빨리 된다.

 

• for문을 n번만큼 돌면서 나눠진 두 구역 중 한 구역만 bfs탐색을 실행한다. 나머지 한구역은 총합에서 bfs탐색 후 나온 값을 빼주면 된다.