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

1. 문제

---

프로그래머스

 

2. 풀이 과정

---

전선을 끊었을 때 두 네트워크 각각의 송전탑 갯수의 차이의 최솟값을 구하는 문제이다.

 

우선 이 문제를 풀려면 그래프를 사용해야한다.

그런 다음 간선을 끊어 생성되는 두 그래프의 노드의 갯수를 세준 뒤 그 차이를 구하고 그 차이의 최솟값을 구하면 된다. 

하지만 실제로는 두 개중 하나의 그래프만 노드의 갯수를 세면 된다. 왜냐하면 노드의 총 갯수를 알고 있기 때문이다.

하나만 세고 다른 하나는 총합에서 빼주면 된다. 

 

따라서 노드의 총합 - 자식트리의 노드 수 - 자식 트리의 노드 수의 최솟값을 구하면 된다. 

 

그래프의 노드의 갯수를 셀때는 그래프를 탐색해야하므로 깊이 우선 탐색 혹은 너비 우선 탐색을 사용할 수 있는데 여기선 최단, 최적을 구하라는 것이 아닌 단순하게 갯수만 세는 것이기 때문에 깊이 우선 탐색을 사용했다.

 

3. 내 코드

---

import java.util.*;
class Solution {

    class Graph {
        int N;
        List<List<Integer>> list;

        Graph(int N) {
            list = new ArrayList<>();
            this.N = N + 1;
            for(int i = 0; i < N + 1; i++) {
                list.add(new ArrayList<>());
            }
        }

        public void addEdge(int src, int dest) {
            list.get(src).add(dest);
            list.get(dest).add(src);
        }

        public List<Integer> getEdges(int src) {
            return list.get(src);
        }
    }

    private Graph initGraph(int n, int[][] edges) {
        Graph graph = new Graph(n);

        for (int[] edge : edges) {
            graph.addEdge(edge[0], edge[1]);
        }

        return graph;
    }
    
    private static Graph graph;
    private static int size;
    private static int NODE_CNT;
    private static boolean[] visited;
    public int solution(int n, int[][] wires) {
        graph = initGraph(n, wires); // 1. 그래프 생성
        size = n;
        
        // 2. 끊어서 송전탑의 갯수 차가 최소가 되는 간선 찾기
        int min = Integer.MAX_VALUE;
        for (int[] wire : wires) {
            int n1 = wire[0];
            int n2 = wire[1];

            int diff = calDiff(n1, n2);
            if (min > diff) 
                min = diff;
        }

        return min;
    }

    private int calDiff(int n1, int n2) {
        NODE_CNT = 0;
        visited = new boolean[size + 1];
        dfs(n1, n2);
        int cnt = NODE_CNT;
        
        return Math.abs(size - 2 * cnt);
    }
    private void dfs(int start, int exct) {

        visited[start] = true;
        NODE_CNT++;
        for(int node: graph.getEdges(start)) {
            if(node == exct || visited[node])
                continue;
            dfs(node, exct);
        }
    }
}

시간 복잡도

• O(N^2)