[프로그래머스] 위클리 9주차 - 전력망을 둘로 나누기(JS)

문제 이해하기

• n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있다. 
• 전선들 중 하나를 끊어서 네트워크를 2개로 분할하려고 한다. 
• 분할된 두 전력망이 갖게 되는 송전탑의 개수를 구해야 한다. 

데이터 추상화

• n개의 송전 탑이 전선을 통해 하나의 트리 형태로 연결되어 있다고 알려주고있다.
• 전선 정보가 2차원 배열로 [ 송전탑, 송전탑] 형식으로 전달된다. 
  예를 들어 [[1,2], [2,3], [3,4]]인 전선 정보가 들어온다면 
  

  

  다음과 같은 모양을 가질 것이다. 
• 위 그림과 같은 그래프를 추상화해보자. 2차원 배열의 행을 송전탑 1, 열을 송전탑 2로 생각해보자. 
  그리고 연결되어 있다면 1이라는 값을 할당하자. 
  

  	0	1	2	3	4
  0	0	0	0	0	0
  1	0	0	1	0	0
  2	0	1	0	1	0
  3	0	0	1	0	1
  4	0	0	0	1	0

  위와 같은 형태로 추상화가 가능하다. 
  

     let ary = Array.from( Array(n+1), ()=> Array(n+1).fill(0));​

• 각 송신탑을 방문했는지 여부를 확인하기 위해서 visit []이 필요하다. 
  

      let visit = Array(n+1).fill(0);​

알고리즘 

1. 입력 파라미터로 wires값이 전달된다. 각 노드들이 연결되어 있음을 구현하자. 앞서 데이터 추상화의 첫 번째 부분에 해당한다. 
   

   // graph mapping
   wires.forEach( ([v1,v2]) => {
     ary[v1][v2] = 1;
     ary[v2][v1] = 1;
   });

2. 이제 전선들 중 하나를 끊어서, 네트워크를 분할한 다음. 연결된 송전탑의 개수를 받자.
   

       ans = wires.reduce( (m, [v1, v2]) => {
       	// 초기화
           cnt = 0; visit.fill(0);
           // 전선 끊기
           ary[v1][v2] = 0;
           ary[v2][v1] = 0;
           // 연결된 송전탑 개수 찾기
           dfs(1);
           // 끊어진 전선 재 연결
           ary[v1][v2] = 1;
           ary[v2][v1] = 1;        
       }, n)

3. 전체 송전탑의 개수에서 연결된 송전탑의 개수를 빼면, 다르게 연결된 송전탑의 개수를 구할 수 있다. 
4. 이 중 가장 적은 값을 반환하면 된다. 
   

    return Math.min(Math.abs(n - cnt - cnt), m );​

구현

function solution(n, wires) {
    let ans;
    var cnt = 0;
    let ary = Array.from( Array(n+1), ()=> Array(n+1).fill(0));
    let visit = Array(n+1).fill(0);
    const dfs = (tower) => {
        ++cnt;
        visit[tower] = 1;
        
        for( let i = 1; i <= n; i++){
            ary[tower][i] && !visit[i] && dfs(i);
        }
    }
    // graph mapping
    wires.forEach( ([v1,v2]) => {
        ary[v1][v2] = 1;
        ary[v2][v1] = 1;
    });
    
    ans = wires.reduce( (m, [v1, v2]) => {
        cnt = 0; visit.fill(0);
        ary[v1][v2] = 0;
        ary[v2][v1] = 0;
        
        dfs(1);
        
        ary[v1][v2] = 1;
        ary[v2][v1] = 1;
        
        return Math.min(Math.abs(n - cnt - cnt), m );
        
    }, n)
    
    return ans;
}

정리 및 느낀 점 

• 이번에 풀어본 문제는 그래프 탐색이다. 그래프를 탐색하는 다양한 방법 중 dfs 방법을 사용하여 구현하였다. 
• 그래프가 연결되어있음을 추상화하는 것이 매우 중요하다. 연결된 각 노드들을 2차원 배열로 매핑해주는 것이 필요하다.
• 방문 여부를 체크할 수 있는 배열을 만들어서 방문 여부를 또한 체크해야 한다. 
• 그래프 탐색 알고리즘도 정리해서 블로깅 하자.

출처

https://programmers.co.kr/learn/courses/30/lessons/86971?language=javascript