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

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

프로그래머스

 

처음 접근한 방법) 

전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않고, 

wires가 정렬되어서 입력되기 때문에, 

끊어낼 전선을 제외한 wires의 가장 처음 원소의 송전탑 번호를 해시셋에 담고, 반복문을 통해 wires를 탐색하며 해시셋에 값이 있는 경우에만 해시에 계속 add 한다면, 결국에는 트리가 이어진 송전탑만 해시에 담길 것이라고 생각했다. 

근데 제시된 테케는 다 통과했지만, 이 후 제출했더니 정확도 20-30이 나옴. ㅎ;  ㅠ

-> 예외 케이스는 뭐가 있을까.. 

import java.util.*;

class Solution {
    
    public int solution(int n, int[][] wires) {
        
        int min_count = 100;
        
        // 와이어 수만큼 bfs 탐색
        for (int i = 0; i < wires.length; i++){
            // i는 끊어낼 wire다. 
            
            int visit = bfs(wires, i, n);
            // 방문한, 방문 안한 노드 수(끊어낸 두 망의 송전탑 개수)가 작은 걸 save
            
            min_count = Math.min(min_count, visit);
        }
    
        return min_count;
    }
    
    static int bfs(int[][] wires, int i, int n){
        // i를 뺀 wires를 순서대로 탐색하며 해시에 넣기
        
        HashSet<Integer> hs = new HashSet<>();
        
        for (int j = 0; j < wires.length; j++){
            // 처음 탐색할 때, 첫번째 노드의 송전탑 번호를 해시에 넣기
            // default로는 첫번째 노드를 해시에 넣지만 i == 0인 경우에만 두번째 노드를 해시에 넣기
            if (j == 0 && i == 0){
                hs.add(wires[1][0]);
                hs.add(wires[1][1]);
            } else if(j == 0){
                hs.add(wires[j][0]);
                hs.add(wires[j][1]);
            }
            
            // 이 후에는 트리 구조라 이어져 있으므로, 해시에 값이 있다면 나머지 값도 계속 해시에 넣어주기
            if (j == i) continue; // 탐색x
            
            if (hs.contains(wires[j][0]) || hs.contains(wires[j][1])){
                hs.add(wires[j][0]);
                hs.add(wires[j][1]);
            }
        }
        
        // return은 송전탑 개수의 차이(절댓값)이 되도록 한다. 
        int count = hs.size();
        int other = n - count;
        return Math.abs(count - other);
    }
}

 

 

다시 푼 방법)

정석으로 풀기 위해 인접리스트를 만들어서 bfs 탐색을 했다. 

인접리스트를 만들기 위해 ArrayList 배열을 만들었다. (ArrayList<int[]> 형태는 많이 사용했는데, 반대의 경우는 처음 구현해봐서 헷갈렸다. 에러 안나게 초기화 꼼꼼히 잘 해주기. )

 

방법은 인접리스트를 만든 후에, wires를 탐색하며, 탐색 원소에 포함된 송전탑 번호들을 인접리스트에서 각자 삭제 해준다. 이렇게 하면 서로의 연결 정보가 사라진다. 

이렇게 정보를 지운 후에 bfs 탐색을 하면서 송전탑 개수를 카운트 하면 된다. 이 때 트리 구조이므로 아무 노드나 넣어도 연결된 것들은 알아서 탐색 되므로, 코드에서는 1번 노드만 계속 넣어줬다. 

 

그 이후에 방식은 처음 접근한 방법과 동일하게 최솟값을 계속 비교하면서 업데이트 해줬다. 

 

import java.util.*;

class Solution {
    static ArrayList<Integer>[] graph;
    
    public int solution(int n, int[][] wires) {
        // 인접리스트 만들기
        // wires.length 만큼 돌면서 해당하는 번호는 서로 지워주기
        // 지웠으면 탐색하기 -> 임의 노드부터 시작하면 알아서 탐색된다. 
        // 탐색 cnt 비교해서 최솟값 업데이트 하기 -> return
        
        graph = new ArrayList[n+1]; // 인덱스 == 전선번호 맞추기 위해 n+1로 하기
        
        // 그래프 ArrayList 초기화. 노드 개수만큼 ArrayList 생성
        for (int i = 0; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        
        // 인접리스트 업데이트 -> 양반향 간선으로 
        for (int i = 0; i < wires.length; i++){
            int v1 = wires[i][0];
            int v2 = wires[i][1];
            
            // 서로의 정보 담아두기
            graph[v1].add(v2);
            graph[v2].add(v1);
        }
        
        // for (int i = 0; i < graph.length; i++){
        //     System.out.println(graph[i]);
        // }
        
        int min = 1000;
        
        // wires.length 만큼 돌면서 해당하는 번호는 서로 지워주고, 탐색하기
        for (int i = 0; i < wires.length; i++){
            int v1 = wires[i][0];
            int v2 = wires[i][1];
            
            // 그래프 복제 하기
            ArrayList<Integer>[] graphCopy = new ArrayList[graph.length];
            
            for (int j= 0; j < graph.length; j++) {
                graphCopy[j] = new ArrayList<>(graph[j]);
            }
            
            graphCopy[v1].remove(Integer.valueOf(v2));
            graphCopy[v2].remove(Integer.valueOf(v1));
            
            boolean visited[] = new boolean[n+1];
            // start 노드, visited 
            // start 노드는 아무거나 설정해도 어쨌든 트리 구조라 이어져있으니까 상관 x
            int cnt = bfs(visited,graphCopy,n);
            
            min = Math.min(cnt, min);
        }
        
        return min;
    }
    
    static int bfs(boolean[] visited, ArrayList<Integer>[] graphCopy, int n){
        
        int cnt = 1; //노드 1포함
        Queue<Integer> q = new LinkedList<>();
        visited[1] = true;
        q.add(1);
        
        while (!q.isEmpty()){
            int num = q.poll();
            ArrayList<Integer> list = graphCopy[num];
            for (int obj : list){
                if (!visited[obj]){// 방문 안했다면
                    visited[obj] = true;
                    cnt++;
                    q.add(obj);
                }
            }
        }
        
        int other = n - cnt;
        return Math.abs(other - cnt);
    }
}