[프로그래머스] 전력망을 둘로 나누기 (Lv 2) - javascript

📝 문제

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.
 
송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.
 

제한사항

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

🤔 실패한 풀이

function solution(n, wires) {

    let obj = {};

    // 각 노드마다 연결된 노드 저장하는 데이터 생성
    for(let i = 0; i < wires.length; i++) {

        if(!(wires[i][0] in obj)) obj[wires[i][0]] = [];
        if(!(wires[i][1] in obj)) obj[wires[i][1]] = [];

        obj[wires[i][0]].push(wires[i][1]);
        obj[wires[i][1]].push(wires[i][0]);
    }

    let answer = Number.MAX_SAFE_INTEGER; // 갯수 차이 넣을 변수

    // 간선 하나씩 끊고 dfs로 각 개수 새기
    for(let i = 0; i < wires.length; i++) {

        // 끊으면 각 노드는 정점이 됨
        let node1 = wires[i][0];
        let node2 = wires[i][1];

        // 각 연결된 리스트에서 뺐다가
        obj[node1].splice(obj[node1].indexOf(node2),1);
        obj[node2].splice(obj[node2].indexOf(node1),1);

        answer = Math.min(Math.abs(dfs(node1, node2) - dfs(node2, node1)), answer);

        // 다시 넣어줌
        obj[node1].push(node2);
        obj[node2].push(node1);
    }

    function dfs(root,anotherRoot) {

        let visited = [];
        let needVisit = [];

        needVisit.push(root);

        while(needVisit.length) {

            let node = needVisit.shift();

            if(!visited.includes(node)) {
                visited.push(node);
                needVisit = [...obj[node], ...needVisit];
            }
        }
        return visited.length;
    }
    return answer;
}

 
평범한 dfs 알고리즘으로 트리를 검색하려니, 제외해야 할 노드의 처리가 힘들었다.
고민하다가 결국 객체에 저장된 리스트에서 서로를 뺐다가 넣었다.
그래도 끝까지 놓지 않고 푸니까 통과할 수 있었다.
좀 더 나은 답이 있을 것 같아서 포기하고 싶더라도,
나의 개떡같은 코드로 끝까지 돌아가게 만드는 것이 중요하다고 느꼈다.
 

• 정확도 테스트 결과

 

🔑 모범 풀이

 

1. wires 그대로 이용하는 풀이

function solution(n, wires) {
   
    let answer = Number.MAX_VALUE; // 비교해서 최소값을 걸러내야 하므로, 제일 큰수로 초기값 세팅
    let cnt = 0; // 아래 while 순회 갯수 셀 변수
    
    // 간선을 하나씩 끊어보자!
    while(cnt !== wires.length) {
        let cur = wires.shift(); // 맨 앞 간선 빼냄
        let node1 = cur[0]; // 각 노드 변수 할당
        let node2 = cur[1]; 
        answer = Math.min(answer, Math.abs(bfs(node1) - bfs(node2))); // 연결된 노드 개수의 차이 구해서 최소값 구해냄
        wires.push(cur); // 빼낸 간선 맨뒤로 넣어줌
        cnt++; // 몇 번 순회 도는지 체크
    }
    
    return answer; // 결국에는 최소값이 남게 된다

    function bfs(node) { // 해당 노드에 연결된 노드 개수 셀 함수 (넓이 우선 탐색)
        let visited = []; // 방문한 노드 저장할 배열
        let needVisit = [node]; // 방문할 노드 저장할 배열
        
        while(needVisit.length !== 0) { 
            let cur = needVisit.shift(); // 현재 노드 빼냄
            wires.forEach(wire => { // 연결되어있는 노드 찾도록 wires 순회
                if(wire.includes(cur)) { // 현재 노드가 포함되어 있다면?
                    let other = wire[0] === cur ? wire[1] : wire[0]; // 연결된 노드 구별해냄
                    if(!visited.includes(other)) needVisit.push(other); // 방문하도록 추가
                }
            })
            visited.push(cur); // 순회 다 돌았으면 방문 완료
        }
        return visited.length; // 연결된 노드들만 남아있으니, 길이 반환
    }

}

 

배열의 값을 그대로 가져와서 사용하는 경우라면 for문보다 forEach를 사용하는 것이 낫다.
그리고 새로운 배열의 반환값이 필요한 경우가 아니라면 map보다 forEach를 사용하는 것이 효율적이다.

 

• 정확도 테스트 결과 

 

2. 새로운 자료형을 만들어서 활용하는 풀이

function solution(n, wires) {

    let obj = {}; // 연결된 노트 저장할 객체 {parent: [child1, child2...], ...}

    wires.forEach(v => { // wires를 순회하며 객체에 값 저장

        let [a,b] = v;

        if(!obj[a]) obj[a] = []; // 프로퍼티가 없다면 생성
        if(!obj[b]) obj[b] = [];

        obj[a].push(b);
        obj[b].push(a);
    })

    let answer = 100; // 나올 수 있는 최대값이 100임

    wires.forEach(v => { // wires를 순회하며 간선을 하나씩 끊어줌
        let [a,b] = v;
        answer = Math.min(Math.abs(search(a, b) - search(b, a)), answer); // 순회할 때마다 최소값이 저장됨
    })

    return answer; // 결과 반환 지점

    function search(root,exception) { // 제거한 간선의 두 노드가 root, exception이 된다

        let count = 0; // 연결된 노드 갯수
        let queue = [root]; // 방문 예정 노드가 저장되는 배열
        let visit = []; // 방문 여부 체크 배열 (idx = root, 값 = 방문 여부)

        while(queue.length) {

            let cur = queue.shift();
            visit[cur] = true; // 방문한 걸로 체크
            count ++; // 연결 노드 개수에 추가해줌

            obj[cur].forEach(child => { // cur에 연결된 노드들 순회
                if(!visit[child] && child !== exception) { // 방문 안했고 & 제외하는 노드 아니면 실행
                    queue.push(child); // 방문하도록 큐에 넣어준다
                }
            })
        }
        return count;
    }
}

 

위 코드보다 간결하지 않지만, 정석적이다.

wires를 순회하며 노드를 key로 하고 연결된 노드를 값으로 저장하는 객체를 만들어 너비 우선 탐색을 실행한다.

속도도 훨씬 빠르다.

 

• 정확도 테스트 결과

 

---

참고

https://dev-note-97.tistory.com/308