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

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

프로그래머스

 

입력

정수 n은 송전탑의 개수
2차원 정수 배열 wires는 각 송전탑을 연결하는 전선 정보

 

핵심 아이디어

모든 간선 중 하나씩 제거해보며 네트워크를 두 개로 분리
각 경우마다 DFS를 통해 한 쪽 네트워크의 노드 수를 구하고
전체 노드 수와 비교해 두 네트워크의 크기 차이를 계산
모든 경우를 탐색하면서 차이의 최솟값을 정답으로 선택

 

변수설명

list는 송전탑 간 연결 정보를 저장하는 인접 리스트
visited는 DFS 방문 여부를 저장하는 배열
cnt는 하나의 네트워크에 속한 송전탑 수
diff는 두 네트워크의 송전탑 개수 차이
dfs 함수는 한 쪽 네트워크에 포함된 송전탑의 개수를 구하기 위해 사용

 

예시

n이 9이고 wires가 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]인 경우
각 간선을 하나씩 제거해 네트워크를 두 개로 나누고
DFS로 한 쪽 크기를 구해 크기 차이 계산
가장 차이가 적은 경우를 찾아 반환
결과는 1

 

정답코드

    public int solution(int n, int[][] wires) {
        int answer = -1;

        // 여기서 노드 간선 하나씩 끊기
        for(int i=0; i<wires.length; i++){

            // 그래프 초기화
            List<List<Integer>> list = new ArrayList<>();
            for (int j = 0; j <= n; j++) {
                list.add(new ArrayList<>());
            }

            // 간선 연결
            for(int j=0; j<wires.length; j++){

                if(i == j) continue;
                int a = wires[j][0];
                int b = wires[j][1];

                list.get(a).add(b);
                list.get(b).add(a);
            }

            int[] visited = new int[n+1];
            Arrays.fill(visited, 0);

            int cnt = dfs(1, list, visited);
            int diff = Math.abs(n - 2 * cnt);
            if (answer == -1 || diff < answer) {
                answer = diff;
            }
        }

        return answer;
    }


    // dfs 는 단순히 연결되어있는 노드 개수 구하는데 사용
    public int dfs(int node, List<List<Integer>> list, int[] visited){

        visited[node] = 1;

        int cnt = 1;

        // 현재 노드와 연결된 간선 탐색
        for(int i : list.get(node)){

            if(visited[i] != 1){
                cnt += dfs(i, list, visited);
            }
        }

        return cnt;
    }