코딩 테스트 [프로그래머스] - 전력망을 둘로 나누기

문제 링크

BFS를 통한 탐색을 통해 문제를 풀었다.

---

전체 코드는 다음과 같다.

import java.util.*;

class Solution {
    
    ArrayList<Integer>[] arrayList;
    boolean[] visited;
        
    public int solution(int n, int[][] wires) {
        int answer = n;
        
        arrayList = new ArrayList[n+1];
        for(int i = 1; i <= n; i++){
            arrayList[i] = new ArrayList<Integer>();
        }
        for(int i = 0; i < wires.length; i++){
            int start = wires[i][0];
            int end = wires[i][1];
            arrayList[start].add(end);
            arrayList[end].add(start);
        }
        
        for(int i = 0; i < wires.length; i++){
            visited = new boolean[n+1];
            int[] deleted = wires[i];
            int count = bfs(deleted);
            int def = n - (count * 2);
            def = Math.abs(def);
            
            answer = Math.min(answer, def);
        }
        
        return answer;
    }
    
    public int bfs(int[] deleted){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        int count = 0;
        
        while(!queue.isEmpty()){
            int start = queue.poll();
            count++;
            visited[start] = true;
            
            for(int i = 0; i < arrayList[start].size(); i++){
                int end = arrayList[start].get(i);
                
                if(start == deleted[0] && end == deleted[1]){
                    continue;
                }else if(end == deleted[0] && start == deleted[1]){
                    continue;
                }else{
                    if(!visited[end])
                        queue.add(end);
                }
                
            }
            
        }
        
        return count;
    }
}

---

정답을 송전탑의 개수로 초기화하였다.

트리의 노드를 ArrayList 배열에 저장하였다.
양방향 노드이기 때문에 양방향으로 저장하였다.

class Solution {
    
    ArrayList<Integer>[] arrayList;
    boolean[] visited;
        
    public int solution(int n, int[][] wires) {
        int answer = n;
        
        arrayList = new ArrayList[n+1];
        for(int i = 1; i <= n; i++){
            arrayList[i] = new ArrayList<Integer>();
        }
        for(int i = 0; i < wires.length; i++){
            int start = wires[i][0];
            int end = wires[i][1];
            arrayList[start].add(end);
            arrayList[end].add(start);
        }

전선의 개수만큼 반복하며
방문 배열을 초기화하고
그 전선을 끊는 전선으로 설정한다.

        for(int i = 0; i < wires.length; i++){
            visited = new boolean[n+1];
            int[] deleted = wires[i];
            ...
        }

끊은 전선을 매개변수로 bfs() 함수를 사용한다.
bfs() 함수는 전선을 끊었을 때 한 전력망의 송전탑의 갯수를 출력하는 함수이다.

        for(int i = 0; i < wires.length; i++){
            visited = new boolean[n+1];
            int[] deleted = wires[i];
            
            int count = bfs(deleted);
            
            ...
        }
        
        ...
    }
    
    public int bfs(int[] deleted){
        ...
    }

bfs() 함수는 BFS 탐색으로 저장한 전선의 연결 배열과 방문 배열을 참고해 탐색을 진행한다.

기본적으로 송전탑은 끊은 전선을 제외하면 모두 연결되있으므로 BFS 탐색을 어디서 시작하는지는 상관이 없으므로 탐색은 송전탑 1부터 시작한다.

탐색을 진행하며 큐에 다음 송전탑을 집어넣을 때, 이 연결이 끊긴 연결인지 확인한다.
연결은 양뱡향 연결이므로 (시작, 도착)의 반대의 경우인 (도착, 시작)과 같은지도 확인하도록 하였다.

탐색을 진행하며 송전탑에 도착했다면 count를 1씩 증가시키고
탐색이 끝나면 count를 반환하여 연결된 송전탑의 개수를 반환한다.

    public int bfs(int[] deleted){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        int count = 0;
        
        while(!queue.isEmpty()){
            int start = queue.poll();
            count++;
            visited[start] = true;
            
            for(int i = 0; i < arrayList[start].size(); i++){
                int end = arrayList[start].get(i);
                
                if(start == deleted[0] && end == deleted[1]){
                    continue;
                }else if(end == deleted[0] && start == deleted[1]){
                    continue;
                }else{
                    if(!visited[end])
                        queue.add(end);
                }
                
            }
            
        }
        
        return count;
    }

bfs()를 통해 연결된 송전탑의 개수를 구했다면 다음은 송전탑의 개수의 차이를 구한다.
나뉜 두 전력망을 A와 B로 가정한다면, 송전탑 개수의 차이는

• 전력망 A가 갖는 송전탑의 개수 - 전력망 B가 갖는 송전탑의 개수

가 되고 이는 다음처럼도 나타낼 수 있다.

• (전체 송전탑의 개수 - 전력망 B가 갖는 송전탑의 개수) - 전력망 B가 갖는 송전탑이 개수

• 전체 송전탑의 개수 - (전력망 B가 갖는 송전탑의 개수 x 2)

그 후 이 값을 절댓값으로 바꾸고,
이 값의 최솟값이 정답이 된다.

        for(int i = 0; i < wires.length; i++){
            visited = new boolean[n+1];
            int[] deleted = wires[i];
            
            int count = bfs(deleted);
            int def = n - (count * 2);
            def = Math.abs(def);
            
            answer = Math.min(answer, def);
        }
        
        return answer;