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

문제

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

알고리즘

bfs

풀이

제한사항을 보면 시간초과가 날 수 없어서 충분히 풀 수 있었는데 너무 오래 걸린 거 같다.

1. 전력망을 하나씩 차단하면서 둘로나눈 전력망의 차이의 절대값을 리턴하고 가장 작은 걸 answer에 담아준다.
2. 전력망을 둘로 나누고 하나의 전력망 개수만 파악하면 나머지는 n-하나의 전력망이기 때문에 wires에서 선택한 전력망의 0, 1 인덱스 중 하나만 선택한다.
3. 선택한 전력망의 인덱스를 가지고 전체 전력망을 순회하면서 부모자리에 있는지, 자식 자리에 있는지 파악한다.
4. 처음에 선택한 전력망을 큐에 담고 3번을 진행하면서 만약 부모자리나 자식 자리에 있으면 큐에 담아주고 카운트를 증가시켜준다.
5. 체크한 전력망은 큐에서 빼주고 체크한 wires의 인덱스로 방문 표시를 해준다.
6. 다 체크했으면 카운트와 n-카운트의 차이의 절대값을 리턴해준다.
7. 6번의 최소값을 계속 구하면 answer가 정답이 된다.

코드

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));
    }
}