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

문제 설명

 

코딩테스트 연습 - 전력망을 둘로 나누기

 

풀이 회고

해당 문제는 BFS를 통해 해결할 수 있었습니다. 우선 해당 문제에서 요구하는 것은 특정 전선을 하나 끊었을 때 두 개로 나뉘어진 전력망의 송전탑의 개수의 차이에 대한 최솟값입니다. 이를 구하기 위해 문제에 접근한 방식으로는 다음과 같습니다.

 

1. 우선 송전탑의 개수 n이 2 또는 3인 경우 결과값이 n - 2로 정해져있으므로 이는 별도 if문으로 결과값을 반환하도록 했습니다.

 

        if (n == 2 || n == 3) {
            return n - 2;
        }

 

2. BFS 탐색을 하기 앞서 전력망 중 임의의 전선 하나를 끊습니다.

 

    public int[][] cutOneWire(int countOfWires, int[][] wires, int i) {
        int[][] twoGrids = new int[countOfWires - 1][2];
        int index = 0;

        for (int j = 0; j < countOfWires; j++) {
            if (j != i) {
                twoGrids[index++] = wires[j];
            }
        }

        return twoGrids;
    }

 

3. 이후 BFS 탐색 시 송전탑(서로 연결된 노드 A와 노드 B) 정보를 저장하는 Target이라는 구조체를 만들고 Queue를 활용하여 전력망을 탐색하면서 Target의 노드들에 포함되는 노드가 있으면 해당 노드들(서로 연결된 노드 정보)을 Queue에 add 시키고 방문 처리 해줍니다.

 

    class Target {
        int nodeA;
        int nodeB;

        public Target(int nodeA, int nodeB) {
            this.nodeA = nodeA;
            this.nodeB = nodeB;
        }

        public boolean containNode(int nodeA, int nodeB) {
            return this.nodeA == nodeA || this.nodeA == nodeB || this.nodeB == nodeA
                || this.nodeB == nodeB;
        }
    }
    
    public int getDifferenceInNumberOfTowers(int[][] twoGrids) {
        Queue<Target> targets = new LinkedList<>();
        targets.add(new Target(twoGrids[0][0], twoGrids[0][1]));

        int countOfTowers = 1; // twoGrids[0]에 대한 송전탑
        int countOfTotalTowers = twoGrids.length;

        boolean[] visited = new boolean[countOfTotalTowers];
        visited[0] = true;

        while (!targets.isEmpty()) {
            Target target = targets.poll();

            for (int i = 1; i < countOfTotalTowers; i++) {
                if (!visited[i] && target.containNode(twoGrids[i][0], twoGrids[i][1])) {
                    visited[i] = true;
                    targets.add(new Target(twoGrids[i][0], twoGrids[i][1]));
                    countOfTowers++;
                }
            }
        }

        return Math.abs(countOfTotalTowers - countOfTowers * 2);
    }

 

4. 해당 전력망에 대해 하나의 전선을 끊을 수 있는 모든 경우에 대해 각각 BFS 탐색을 하면서 송전탑의 개수의 차이가 최소인 경우를 구합니다.

 

        double result = Double.POSITIVE_INFINITY;
        
        int countOfWires = wires.length;

        for (int i = 0; i < countOfWires; i++) {
            int[][] twoGrids = cutOneWire(countOfWires, wires, i);
            int differenceInNumberOfGrids = getDifferenceInNumberOfTowers(twoGrids);
            result = result < differenceInNumberOfGrids ? result : differenceInNumberOfGrids;
        }

 

 

전체 소스 코드

import java.util.LinkedList;
import java.util.Queue;

class Solution {

    class Target {
        int nodeA;
        int nodeB;

        public Target(int nodeA, int nodeB) {
            this.nodeA = nodeA;
            this.nodeB = nodeB;
        }

        public boolean containNode(int nodeA, int nodeB) {
            return this.nodeA == nodeA || this.nodeA == nodeB || this.nodeB == nodeA
                || this.nodeB == nodeB;
        }
    }

    double result = Double.POSITIVE_INFINITY;

    public int solution(int n, int[][] wires) {
        if (n == 2 || n == 3) {
            return n - 2;
        }

        int countOfWires = wires.length;

        for (int i = 0; i < countOfWires; i++) {
            int[][] twoGrids = cutOneWire(countOfWires, wires, i);
            int differenceInNumberOfGrids = getDifferenceInNumberOfTowers(twoGrids);
            result = result < differenceInNumberOfGrids ? result : differenceInNumberOfGrids;
        }

        return (int) result;
    }

    public int[][] cutOneWire(int countOfWires, int[][] wires, int i) {
        int[][] twoGrids = new int[countOfWires - 1][2];
        int index = 0;

        for (int j = 0; j < countOfWires; j++) {
            if (j != i) {
                twoGrids[index++] = wires[j];
            }
        }

        return twoGrids;
    }

    public int getDifferenceInNumberOfTowers(int[][] twoGrids) {
        Queue<Target> targets = new LinkedList<>();
        targets.add(new Target(twoGrids[0][0], twoGrids[0][1]));

        int countOfTowers = 1; // twoGrids[0]에 대한 송전탑
        int countOfTotalTowers = twoGrids.length;

        boolean[] visited = new boolean[countOfTotalTowers];
        visited[0] = true;

        while (!targets.isEmpty()) {
            Target target = targets.poll();

            for (int i = 1; i < countOfTotalTowers; i++) {
                if (!visited[i] && target.containNode(twoGrids[i][0], twoGrids[i][1])) {
                    visited[i] = true;
                    targets.add(new Target(twoGrids[i][0], twoGrids[i][1]));
                    countOfTowers++;
                }
            }
        }

        return Math.abs(countOfTotalTowers - countOfTowers * 2);
    }
}

 

 

참고자료

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