전력망을 둘로 나누기

1. 전력망(친구목록)을 만들어 줍니다.
   

      function solution(n, wires) {
          const network = Array.from({length:n+1},()=>[])
          
          wires.forEach((item,i)=>{
            const [from, to] = item;
            network[from].push(to);
            network[to].push(from);  
          })
      }

---

그림 설명

2. 전력망에서 1개씩 끊어서, 2개의 전력망으로 나눈다.
   ⇒ 그러면 어떻게 끊고, 어떻게 나누나?
   ⇒ 순차적으로 한명씩 새로운 카톡방(A카톡방)에 담아서 연결을 끊는다.
   ⇒ 순차적으로 끊어 새로운방에 담은 그 친구의 친구들을 A카톡방에 추가해서 나눔

• 1⇒2 , 2⇒3, 3⇒4 이 부분을 순차적으로 절교를 한다고 약속 합시다.
  ** 어떻게 끊어주나?? ****

  1. 1번째 친구부터 한명씩 A번 단톡방 담아줍니다.
  2. 절교할 친구를 제외하고, 나머지 친구들을 새로운 전력망(A번 단톡방)에 담아줍니다.
     이게 뭔 소리냐??
  3. 단 아래의 내용을 보기전에 2가지 약속(?) 하고 갑시다
     1. 이해를 위해 친구, 절교 라는 단어를 사용
     2. 하루가 지나면 화해를 하기 때문에, 친구목록은 변하지 않음 (처음에 입력값으로 만든 부분)

• 1번 , 2번이 절교 ⇒ A카톡방 1명 - B카톡방 3명 ⇒ 2명 차이

---

• 2번과 3번이 절교 ⇒ A카톡방 2명 - B카톡방 2명 ⇒ 0명 차이
• 중요한 부분은 절교를 한 친구라서 무조건 절교를 한 친구 먼저 A 카톡방에 넣어줍니다.
  

---

• 3번과 4번이 절교 ⇒ A카톡방 3명 - B 카톡방 1명 ⇒ 2명차이
• 중요한 부분은 절교를 한 친구라서 무조건 절교를 한 친구 먼저 A 카톡방에 넣어줍니다.
  

• 단 주의할점은 위의 예시에서는 절교를 하는 순서가 1-2-3-4 순서인데 무조건 1-2-3-4 순서가 아니라,
  입력값에서 주어진 목록을 기준으로 하는것 .
• 위의 문제에서는 입력값에서 주어진 목록이 1-2-3-4 순서였기 때문에 1-2-3-4 순서로 진행
• 이게 뭔소리냐? 아래의 예시에서 절교하는 순서가 1-2-3-4-5-…9 순서가 아니다.
  • 무조건 1-2-3-4 순서가 아니라 문제에서 주어진 친구목록에서 정점의 순서대로 절교를 해준다.
  • 예를들어 정점의 순서는 1,2,3,4,5,6,… 이다.
  • 정점의 순서대로 1과 연결된 친구를 끊어줌 1 - 3 1과2를 끊는것이 아님
  • 정점의 순서대로 2와 연결된 친구를 끊어줌 2 - 3
  • 정점의 순서대로 3과 연결된 친구를 끊어줌 3 - 4

그럼 코드를 보며 확인해보겠습니다. 예시를 위해 코드를 바꿔봤는데, 예시가 마음에 안든다 or 이해가 안된다
하시면 바로 밑에 정답코드가 있으니 확인해보시면 되겠습니다.

코드 설명

	
		// 0번째 부터 순차적으로 절교를 하고, 각 카톡방의 인원수 차이가 최소가 되는 경우를 찾는다. 
    for(let i=0; i<wires.length; i++){
        min=Math.min(min, getDiff(i));     
    }
    return min;

    function getDiff(index) {
			// leftConnection === A 카톡방   
			// 단 1번의 친구가 2번이고, 3번의 친구가 2번이면 두번 초대하지 말고 한명만 하자~ 
	    let leftConnection = new Set();
			
			// from, to는 절교할 예정인 친구를 의미,  index번째 날에 from, to는 절교한다. 
			// Ex) let [2,3] = wires[index] => 2번과 3번은 index번째 날에 절교할 예정
	    let [from, to] = wires[index];
			
      // from, to는 절교를 했기 때문에 from 친구가 A단톡방을 만듦
	    leftConnection.add(from);
	
	    // 현재 A카톡방에 있는 친구들에게 각자 친구를 초대하라는 코드 
			// for(소속된 친구 of A카톡방){   
	    for (let v of leftConnection) {

				// 소속된 친구들은 각자 친구목록에서 초대할 사람을 확인해봄
	      network[v].forEach((value) => {
	
					// 초대할 친구가 절교할 친구가 아닌경우
	        if (value !== to) {
						// A 단톡방에 초대!!  
	          leftConnection.add(value);
	        }
	      });
	    }
		// 총 친구 목록에서 A카톡방에 있는 친구 * 2를 뺀 경우가 A카톡방과 B카톡방의 인원수 차이 
    return Math.abs(n - leftConnection.size * 2);
  }
}

최종 정답 코드

// 1. 전력망을 만들어줍니다.
// 2. 전력망에서 한개씩 끊어서 2개의 전력망으로 나눠줍니다.
// 3. 2개의 전력망의 각각 송전탑의 개수의 차이를 구하고, 차이값의 최소를 구해줍니다.

function solution(n, wires) {
    const network = Array.from({length:n+1},()=>[])
    
    wires.forEach((item,i)=>{
      const [from, to] = item;
      network[from].push(to);
      network[to].push(from);  
    })
    let min = 100;
    
    for(let i=0; i<wires.length; i++){
        min=Math.min(min, getDiff(i));     
    }
    
    return min;
    
    function getDiff(index) {
    let leftConnection = new Set();
    let [from, to] = wires[index];
 
   leftConnection.add(from);
        
    for (let v of leftConnection) {
      network[v].forEach((value) => {

        if (value !== to) {
          leftConnection.add(value);
        }
      });
    }
    return Math.abs(n - leftConnection.size * 2);
  }
}