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

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

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

프로그래머스

문제 설명

전력망이 트리의 형태로 주어지는데 이중 하나의 간선을 잘라서 두개의 전력망으로 나눴을 때

각 개수의 차이가 가장 작을 때의 값을 구하는 문제이다.

---

문제 풀이

생각 과정

전력망의 개수가 최대 100개로 주어졌으므로 완전탐색으로 모든 간선들을 순회하며 각 간선들이 잘렸을 때마다 생기는 개수의 차이를 갱신해주는 방식으로 생각을 했다.

 

하나의 간선을 잘랐을 때 해당 간선에는 두개의 노드가 있게 된다.

이 두개의 노드가 나눠진 전력망의 각각 시작 노드가 된다.

큐를 하나 생성하고 그 안에 시작노드를 넣는다. 그리고 아래 과정을 반복한다.

1. 노드를 하나 꺼낸다.

2. 연결되어있는 노드를 세며 방문체크를 하고 연결되어있는 노드를 다시 큐에 넣는다.

3. 큐가 빌 때까지 반복한다.

 

자세한것은 아래 코드로 확인해보자.

구현

public class 완전탐색_전력망둘로나누기 {
    static class Solution {
        static int ans; // 답
        static List<Integer>[] list;    // 각 노드에 연결된 다른 노드 개수
        public int solution(int n, int[][] wires) {
            ans = Integer.MAX_VALUE;    // 최소값을 구해야하므로 초기값을 최대로
            list = new ArrayList[101];  // 송전탑의 개수는 최대 100개
            for (int i = 0; i < 101; i++) {
                list[i] = new ArrayList<>();
            }
            for (int i = 0; i < wires.length; i++) {
                int v1 = wires[i][0];
                int v2 = wires[i][1];
                list[v1].add(v2);   // 양방향 그래프이므로 둘다 넣어줌
                list[v2].add(v1);
            }
            for (int i = 0; i < wires.length; i++) {
                int v1 = wires[i][0];
                int v2 = wires[i][1];
                cut(v1,v2);
            }
            return ans;
        }
        
        public void cut(int v1, int v2){
            int cnt1 = count(v1,v2);    // v1에서부터 연결된 노드의 개수
            int cnt2 = count(v2,v1);    // v2에서부터 연결된 노드의 개수
            ans = Math.min(ans, Math.abs(cnt1 - cnt2)); // 최솟값 갱신
        }

        public int count(int v1,int v2) {
            int cnt = 1;
            Queue<Integer> q = new LinkedList<>();
            q.add(v1);
            boolean[] visited = new boolean[list.length];
            visited[v1] = true; // 중복방지를 위한 배열
            while(!q.isEmpty()){
                int cur = q.poll(); // 현재 노드
                for (int i = 0; i < list[cur].size(); i++) {
                    int next = list[cur].get(i);    // 연결된 노드를 다시 큐에 넣으면서 개수구하기
                    if (visited[next] || next==v2) continue;    // v2는 끊어졌으므로 넘어가기
                    visited[next] = true;
                    q.add(list[cur].get(i));
                    cnt++;
                }
            }
            return cnt;
        }
    }
}

주의점

완전탐색에서 항상 주의해야하는 visit 체크만 생각해주면 될 것 같다.