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

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

프로그래머스

 

사용 알고리즘

• 완전 탐색
• 그래프 탐색
• BFS

풀이

 

import java.util.*;
class Solution {
    static List<List<Integer>> graph = new ArrayList<>();
    static boolean[] visited;
    static int min = Integer.MAX_VALUE;
    public int solution(int n, int[][] wires) {
        int answer = -1;
        
        for(int i = 0; i <= n ; i++) {
            graph.add(new ArrayList<>());
        }
        
        
        for(int [] wire : wires) {
            int u = wire[0];
            int v = wire[1];
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        
        for(int [] wire : wires) {
            int u = wire[0];
            int v = wire[1];
            graph.get(u).remove((Integer) v);
            graph.get(v).remove((Integer) u); 
            
            visited = new boolean[n + 1];
            int count = bfs(u, visited);
            int count2 = n - count;
            
            min = Math.min(min, Math.abs(count - count2));
            
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        return min;
    }
    
    public int bfs(int start, boolean [] visited) {
        int cnt = 0;
        visited[start] = true;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        
        while(!queue.isEmpty()) {
            int node = queue.poll();
            cnt++;
            for(int next : graph.get(node)) {
                if (visited[next]) continue;
                visited[next] = true;
                queue.add(next);
            }
        }
        return cnt;
    }
}

 

회고

 

[[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 입력값이 이렇게 주어질 때, 처음부터 두 정점의 간선을 끊고 bfs를 돌리면서 정점의 개수를 계산하면 되는 문제였다.

 

문제를 풀면서 간선을 어떻게 끊을까? 이부분에 대해서 고민하다가 풀이를 찾아봤다 

graph.get(u).remove((Integer) v);
graph.get(v).remove((Integer) u); 
// Integer.valueOf()도 사용 가능

 

나는 단순하게 생각해서

graph.get(u).remove(v);

이렇게 로직을 짰지만, [1,3]일때를 생각해보면 정점 1에 연결되어 있는 3번째 인덱스를 제거하란 뜻과 동일하다. 당연히 3번쨰 인덱스까진 가지 않으니 OutofBounds 에러가 발생한다.

 

반면에, Integer로 형변환 해주면, 값이 v인 첫번째 요소를 제거하는 것이 된다. 즉, 값이 3인 정점을 성공적으로 제거할 수 있다.

 

이부분 꼭 기억하자!

그 외의 로직은, 연결을 끊었을 때 끊은 정점 (u)부터 bfs를 돌리면서 연결되어 있는 간선의 개수를 파악했고, 다른 송전탑에서 연결되어 있는 간선의 개수는 총합(n) - bfs(u)가 되므로 문제 요구사항에 맞게 최솟값을 갱신해주면 되었다.

 

그리고, 마지막에 끊었던 간선을 연결해줘야 순차적으로 bfs를 돌릴 수 있다.

 

아이디어까진 떠올렸으나, 자바 기본 문법에서 시간을 허비한게 좀 아쉬웠다. 

 

다중리스트 기본ㅁ 문법

• 다중 리스트 생성: List<List<Integer>> multiList = new ArrayList<>();
• 요소 추가: multiList.get(outerIndex).add(value);
• 요소 접근 및 수정: multiList.get(outerIndex).get(innerIndex);
• 요소 삭제: multiList.get(outerIndex).remove((Integer) value);