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

 

 

문제 파악

-서로 이어져있는 그래프의 간선을 ‘하나’ 끊었을 때, 두 개로 나누어진 그래프를 각각 순회

-순회 시 방문 노드를 카운트하여 리턴하고, 각 순회가 끝났을 때 두 그룹의 카운트 차를 비교

-최솟값을 갱신하여 최종 리턴

• n은 2 이상 100 이하인 자연수입니다.
• wires는 길이가 n-1인 정수형 2차원 배열입니다.
  • wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
  • 1 ≤ v1 < v2 ≤ n 입니다.
  • 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.

접근 방법

💡 -BFS를 이용하여 각 노드를 순회 -그래프를 둘로 쪼갤 때 ⇒ 간선을 순회하며 하나씩 다 삭제해보기(O(n))

-인접리스트 형태로 변환한 그래프를 가지고 for문 돌며 비교 연산 수행한다.

-최솟값은 Integer.MAX_VALUE값으로 초기화해놓았다가, 더 작은 값이 나오면 갱신하는 방식으로 반복.

-BFS는 노드를 방문하기만 하면 카운트하게끔 단순히 cnt변수를 두어 후위연산자로 증가시키고 큐가 비어서 순회를 마무리할 때 리턴

 

*포인트

graph.get(w[0]).remove(Integer.valueOf(w[1]));

graph.get(w[1]).remove(Integer.valueOf(w[0]));

이 부분에서 Integer.valueOf() 로 형변환을 반드시 해주어야 한다.

리스트에는 int형태로 들어있어 그냥 넣게 되면 remove함수가 인덱스 값으로 인식하기 때문. 어떤 객체의 값 자체로 제거하고 싶다면 Object형태로 인자를 넘겨줘야함.

 

코드 구현

import java.util.*;

class Solution {
    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE;
        Map<Integer,List<Integer>> graph = new HashMap<>();
        //인접리스트
        for(int i=0;i<wires.length;i++){
            int w=wires[i][0];int m=wires[i][1];
            graph.putIfAbsent(w,new ArrayList<>());
            graph.putIfAbsent(m,new ArrayList<>());
            graph.get(w).add(m);graph.get(m).add(w);
        }
        
        for(int[] w:wires){
            graph.get(w[0]).remove(Integer.valueOf(w[1]));
            graph.get(w[1]).remove(Integer.valueOf(w[0]));
            int first = bfs(w[0],graph,n);//끊고 첫 그룹 순회 return : 간선 갯수
            int second = n-first;
            
            answer = Math.min(answer,Math.abs(first-second));
            graph.get(w[0]).add(w[1]);
            graph.get(w[1]).add(w[0]);
        }
        
        
        return answer;
    }
    public int bfs(int start,Map<Integer,List<Integer>> graph,int n){
        Queue<Integer> que = new ArrayDeque<>();
        boolean[] visited = new boolean[n+1];
        que.offer(start);
        visited[start]=true;
        int cnt=0;
        while(!que.isEmpty()){
            int number = que.poll();
            cnt++;
            
            for(int x:graph.get(number)){
                if(!visited[x]){
                    que.offer(x);
                    visited[x]=true;
                }
            }
        }
        return cnt;
    }
}

 

배우게 된 점

-그래프를 둘로 쪼갤 때, 주어진 n을 2로 나누어 그 값에 가깝게 그래프가 만들어지면 그 값을 리턴해야하나 생각했는데 사실은 사칙연산으로 가능한 건 최대한 간단하게 처리하는 게 좋은 것이었다.

그냥 for문으로 O(n)번 간선을 완전 탐색하며 간선을 삭제-bfs연산-비교-다시 삽입을 반복하는건데

간단하지만 확실하고 깔끔한 방법인 것 같다. -remove() 사용법을 제대로 알 수 있었다.