[프로그래머스, 자바] Level2:전력망을 둘로 나누기 (위클리 챌린지 9주차)

문제분석

목표:  어떤 간선을 잘랐을때, 나누어진 두개의 전력망의 차이가 최소가되는 경우구하기

 

간선을 잘랐을때, 두개의 전력망의 차이가 최소가 되는경우를 구해야하기때문에

일단, 간선을 하나씩은 다 잘라봐야한다. (완전탐색)

 

간선을 자르는행위는, wires간선에 원소를 없애버려야한다. 

하지만, 입력값을 건드릴수는 없으니... wires배열의 복사본으로 List를 선언했다.

 

BFS탐색을위해, Queue를 선언한다. (이유: 간선이 연결되어있는걸 탐색하기위해)

 

예시를 하나 들어보자면, wires간선에 [4,7]을 자르기로했다. 그러면,

List=[[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 이 되어야한다.

 

자르고나면, 왼쪽이든 오른쪽이든 갯수를 세어야한다.

 

본인은 부모(왼쪽)를 기준으로 세기로하였다.

간선 [4,7]의 부모는 4다.    

부모 4를 초기값으로 Queue에 넣는다.

 

초기값을 설정했으면, Queue가 비어있을때까지 무한루프를 돌린다.

이때, Queue에서 원소를 뽑을때마다, 카운트(전력망갯수) 1씩늘린다. 

 

4는, 부모가될수도있고, [4,5] , [4,6]

      자식이 될수도있다.[3,4]

 

부모가 될때 간선 [4,5] ,[4,6] 을 자르고, 자식들을 큐에넣는다. 큐 (5,6)

List=[[1,3],[2,3],[3,4],[4,5],[4,6],[7,8],[7,9]]

자식이 될때 간선 [3,4] 을 자르고, 부모(3)를 큐에 넣는다. 큐(5,6,3) 

List=[[1,3],[2,3],[3,4],[7,8],[7,9]]

 

그다음엔 큐에서 5를 뽑고 5가 부모or자식이 되는지를 확인한다.(반복)

 

큐가 비어있을때까지 모두 완료했다면, 하나의 간선작업이끝난것이다.

 

하나의 간선작업이 모두끝났다면, 두개의 연락망의 차이가 최소가 되는점을 구한다.

 

그림으로 보면 이렇다.

대략적인 코드가 돌아가는 구성

문제풀이

import java.util.*;
class Solution {
    public int solution(int n, int[][] wires) {
        int answer = 101;
        int val1=0;
        int val2=0;
        for(int i=0;i<wires.length;i++){
            val1=relationCnt(i,wires);
            val2=n-val1;
            int total=Math.abs(val1-val2);
            answer=Math.min(total,answer);
        }
        
        return answer;
    }
    
    public int relationCnt (int idx, int[][] wires){
        
        Queue<Integer> que = new LinkedList<>();
        List<int[]> list = new ArrayList<>();
        for(int[] data:wires){
            list.add(data);
        }
        
        int parent=list.get(idx)[0];
        que.add(parent);
        list.remove(idx);
        int cnt=0;
        
        while(!que.isEmpty()){
          int temp=que.remove();           
          for(int i=0;i<list.size();i++){
              int[] arr= list.get(i);
              boolean flag=true;
              if(arr[1]==temp){
                  que.add(arr[0]);
                  list.remove(arr);
                  flag=false;
              }
              if(arr[0]==temp){
                  que.add(arr[1]);     
                  list.remove(arr);  
                  flag=false;
              }   
             if(flag==false){
                 i--;
             }
          }
          cnt++;
        }
        return cnt;
    }
}

 

// 45~47줄에 flag==false일때 i--를 한이유:

List를 순회하는 도중에, List의 원소를 제거해버리면, 리스트의 idx가 한칸씩줄고,

다음 반복을할때 idx가 1증가한다. (이렇게되면 간선 하나를 놓쳐버린다!)

이 현상을 방지하기위해, 삭제가일어나면(flag==false),

i값을 하나 줄이는걸로 간선을 놓치지 않도록 코딩을 하였다.