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

코딩테스트 연습 - 전력망을 둘로 나누기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

- DFS를 활용해서 해당되는 경우의 수를 구한 후에 이를 활용해서 나머지 방문하지 않은 노드의 갯수를 구한 후에 그 둘의 차이가 가장 적은 값을 리턴하는 문제이다.

 

class Solution {
    int[][] wires;
    int cnt = 0;
    int mini = Integer.MAX_VALUE;
    public int solution(int n, int[][] wires) {
        this.wires = wires;
        int[] arr = new int[n];
        for(int i = 0; i < wires.length; i++) {
            cnt = 0;
            dfs(arr, wires[i][1], i);
            int max = Math.max(arr.length - cnt, cnt);
            int min = Math.min(arr.length - cnt, cnt);
            mini = Math.min(mini, max - min);
            arr = new int[n];
        }
        return mini;
    }

    void dfs(int[] arr, int n, int n2) {
        if(arr[n - 1] == 1 || n == wires[n2][0])
            return;
        cnt++;
        arr[n - 1] = 1;
        for(int i = 0; i < wires.length; i++) {
            if(wires[i][0] == n) {
                dfs(arr, wires[i][1], n2);
            } else if(wires[i][1] == n) {
                dfs(arr, wires[i][0], n2);
            }
        }
    }
}

정확성 테스트

테스트 1 〉	통과 (5.44ms, 72.3MB)
테스트 2 〉	통과 (4.42ms, 79.4MB)
테스트 3 〉	통과 (0.95ms, 74.5MB)
테스트 4 〉	통과 (0.79ms, 73.1MB)
테스트 5 〉	통과 (0.83ms, 80.8MB)
테스트 6 〉	통과 (0.10ms, 71MB)
테스트 7 〉	통과 (0.05ms, 86.7MB)
테스트 8 〉	통과 (0.23ms, 78.3MB)
테스트 9 〉	통과 (0.20ms, 76.4MB)
테스트 10 〉	통과 (3.46ms, 80.4MB)
테스트 11 〉	통과 (4.73ms, 73MB)
테스트 12 〉	통과 (3.85ms, 76MB)
테스트 13 〉	통과 (3.53ms, 76.2MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0