[JS] 전력망을 둘로 나누기

 

 

난이도: Lv. 2

정답률: 49%

문제: https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

 

 

알고리즘

1. key는 송전탑의 번호, value는 key 송전탑과 연결된 모든 송전탑을 담은 배열인 객체를 만든다.
2. 전선을 하나씩 끊는다.
   1. 끊은 전선인 송전탑 두 개를 set에 넣는다.
   2. 첫 번째 송전탑과 연결된 모든 송전탑을 스택에 넣는다.
   3. 스택에 있는 송전탑을 하나씩 꺼내면서 set에 존재하는지 확인한다. 즉, 이미 방문했던 송전탑인지 확인한다.
   4. 방문하지 않았다면 해당 송전탑을 set에 넣고, 해당 송전탑과 연결된 모든 송전탑을 스택에 넣는다.
3. set의 size를 이용하여 두 전력망이 가지고 있는 송전탑 개수의 차이를 구한다. 현재 set은 끊긴 전선의 두 번째 송전탑도 포함하고 있음을 유의해야 한다.
4. 2와 3의 과정을 반복하여 최솟값을 찾는다.

 

 

코드

function solution(n, wires) {
    let answer = 100;
    const graph = {};

    for (let wire of wires) {
        const [tower1, tower2] = wire;

        if (graph[tower1]) { graph[tower1].push(tower2); }
        else { graph[tower1] = [tower2]; }

        if (graph[tower2]) { graph[tower2].push(tower1); }
        else { graph[tower2] = [tower1]; }
    }

    for (let removedWire of wires) {
        const [startTower, endTower] = removedWire
        const visitedSet = new Set([startTower, endTower]);
        const stack = [...graph[startTower]];

        while (stack.length) {
            const tower = stack.pop();

            if (!visitedSet.has(tower)) {
                visitedSet.add(tower);
                stack.push(...graph[tower]);
            }
        }

        const diff = Math.abs(2 * (visitedSet.size - 1) - n);
        if (answer > diff) { answer = diff; }
    }

    return answer;
}

 

 

주저리

처음 짠 코드

function solution(n, wires) {
    let answer = 100;

    wires.sort((a, b) => {
        const result = a[0] - b[0];
        if (!result) { return a[1] - b[1]; }
        else { return result; }
    });

    for (let removeIdx = 0; removeIdx < wires.length; removeIdx++) {
        const set = new Set();

        for (let wireIdx = 0; wireIdx < wires.length; wireIdx++) {
            if (removeIdx === wireIdx) { continue; }

            const tower1 = wires[wireIdx][0];
            const tower2 = wires[wireIdx][1];

            if (!set.size) {
                set.add(tower1);
                set.add(tower2);
                continue;
            }

            if (set.has(tower1) || set.has(tower2)) {
                set.add(tower1);
                set.add(tower2);
            } else {
                break;
            }
        }

        const diff = Math.abs(set.size - (n - set.size));
        if (answer > diff)
            answer = diff;
    }

    return answer;
}

처음에는 set 두개로 풀려고 했다. 근데 테케 3개만 맞길래 왜 안 되는 지도 모르고 몇 시간 머리 굴렸다. 진짜 한참 생각해 보니까 [[1, 4], [2, 3]. [2. 4]] 이런 경우를 못 잡아낸다.

그래서 dfs로 풀어보려고도 했는데 재귀 함수를 어떻게 돌릴지 감도 안 잡혀서 또 몇 시간 헤매다가 결국엔 다른 사람 코드를 좀 봤다. 그래서 글 안 올리려고 했는데 그래도 일단은 올린다............

dfs는 무조건 재귀 함수일 거라는 편견 때문에 못 풀었던 것 같다. 그래서 저분 코드보고 진짜 천재라고 생각했다.........