[プログラマー]電力網を二つに分ける

質問する

アルゴリズム#アルゴリズム#

に答える

コード#コード#

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE;

		// 전체 전력망을 돌면서 두 전력망의 차이를 구한다.
        for (int i = 0; i < wires.length; i++) {
            answer = Math.min(answer, bfs(n, i, wires));
        }

        return answer;
    }

    public int bfs(int n, int index, int[][] wires) {
        int[] visit = new int[n];
        Queue<Integer> q = new LinkedList<>();

        visit[index] = 1;
        int cnt = 1;

		// 차단할 전력망의 0, 1 중에 하나의 전력망 개수만 구해준다.
        q.offer(wires[index][1]);

        while (!q.isEmpty()) {
        
        	// 큐에서 하나 빼준다.
            Integer pointer = q.poll();

            for (int i = 0; i < n - 1; i++) {
            
            	// 방문하지 않았는지 체크
                if (visit[i] == 0) {
                
                	// 부모자리의 값과 포인터 값이 같은지 확인한다.
                    // 만약 같으면 해당 자리의 반대편 값을 큐에 넣어준다.
                    if (wires[i][0] == pointer) {
                        q.offer(wires[i][1]);
                        visit[i] = 1;
                        cnt++;
                    }

					// 자식자리의 값과 포인터 값이 같은지 확인한다.
                    // 만약 같으면 해당 자리의 반대편 값을 큐에 넣어준다.
                    if (wires[i][1] == pointer) {
                        q.offer(wires[i][0]);
                        visit[i] = 1;
                        cnt++;
                    }
                }
            }
        }

		// 둘로 나눈 전력망의 차이의 절대값을 리턴해준다.
        return Math.abs(cnt - (n - cnt));
    }
}