[프로그래머스] Level2 - 전력망을 둘로 나누기(Javascript)

프로그래머스

▶ 문제 요약

1. n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 한다. 

2. 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 한다.

3. 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

 

▶ 정답 코드

function solution(n, wires) {
    let answer = Number.MAX_VALUE
    // 인접리스트를 위해서 빈 배열을 n+1 크기만큼 만든다.
    let graph = Array.from(Array(n+1),() => []);
    
    // wires의 길이만큼 돌면서
    for (let i = 0; i < wires.length; i++) {
    	// 인접리스트 생성
        let [n1, n2] = wires[i];
        graph[n1].push(n2);
    	graph[n2].push(n1);
    }
    
    // dfs 함수 생성
    function dfs(v, visited) {
        // 시작 방문 처리
        visited[v] = true;
        // 송전탑의 개수
        let tower = 1;
        
        // 인접노드를 돌면서
        for (const adj of graph[v]) {
           // 방문하지 않았던 곳이면
           if (!visited[adj]) {
              // 재귀적으로 함수를 다시 돌려서 송전탑의 개수를 쌓아올린다.
           	  tower += dfs(adj, visited);
           }
        }
        return tower;
    }
    
    // 전력망 비교
    for (const wire of wires) {
        let [n1, n2] = wire;
        // 방문 표시 배열
        let visited = Array(n+1).fill(false);
        
        // 그리고 전선자르기 
        graph[n1] = graph[n1].filter(a => a !== n2);
        graph[n2] = graph[n2].filter(b => b !== n1);
        
        // 두 개의 전선의 송전탑 개수 구하기
        let node1 = dfs(n1, visited);
        let node2 = dfs(n2, visited);
        
        // 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)
        const diff = Math.abs(node2 - node1);
        
        // 최솟값 갱신
    	if (diff < answer) answer = diff;
        
        // 다음 송전탑 비교하기 위해서 없앴던 것들 원상 복구
        graph[n1].push(n2);
        graph[n2].push(n1);
    }
    
    return answer;
    

}

▶ 풀이 과정

1. 서로 연결되어 있는지 체크하려면 인접리스트를 활용해야 한다. 그래서 Array.from()을 활용해서 빈 배열을 n+1만큼 만든다. 배열의 인덱스는 0부터 시작 그러나 여기서는 1번 노드부터 봐야하니까 n+1을 해줬다.

 

2. wires의 길이만큼 돌면서 배열 안에 인접 노드들을 채운다. 양방향으로 채운다.

 

3. dfs함수를 생성한다. 시작 방문처리 해주고 송전탑의 개수를 구해야하니 일단 시작할때 본인 전력망은 포함시켜야 하니까 1로 시작한다. 그리고 인접 노드를 돌아주면서 방문하지 않았다면 그 부분을 더 파고든다. 재귀적으로. 그렇게해서 연결되어 있는 부분까지 재귀로 돌면서 tower를 하나씩 쌓아준다. 

 

4. 이제 전력망을 비교해준다. for of문을 사용해서 wires를 돌면서 두 개의 전선을 뽑아낸다. 방문리스트는 다음 wire가 들어올때마다 새로 발급된다.

 

5. 오늘 문제의 핵심 전선 자르기! 방법은 현재 내가 인접하고 있는 노드 중에서 끊어야 하는 노드를 filter() 메서드를 활용해서 거른다. 

 

6. 두 개의 송전탑 개수를 구해주고 절댓값 함수를 활용해서 두 개의 차이를 구한다. 

 

7. 그렇게 해서 수의 최댓값으로 설정해놓은 answer과 비교해서 더 작으면 값을 갱신하도록 조치해준다. 

 

8. 자 그리고 또 핵심..!! 끊어야 하는 노드를 끊었으면 다른 두 송전탑이 서로 올바르게 비교할 수 있게 원상복구 시켜야한다. 그래서 다시 서로 지운 노드를 인접 노드로 넣어준다.