[프로그래머스]전력망을 둘로 나누기

📖 문제

level2 전력망을 둘로 나누기

✏️ 나의 풀이

완전탐색이라는것을 알려주지 않았으면 어떤식으로 접근하기 어려웠을 것 같은 문제였다.

우선 bfs 로 풀어야지 라는 마음으로 bfs 코드를 작성하고나니 어떤식으로 전력망을 두개로 나누어야 하는지 고민하게 되었다.

그렇게 문제를 계속 읽던 중 완전탐색 문제라는 것이 표시되어 있어 모든 경우의 수를 전부 확인해보는 방법으로 코드를 작성했다.

또한, n은 100 이하인 자연수이므로 완전탐색을 해도 큰 문제가 없을 것 같았다. 그래서 완전 탐색 문제인가…

그렇게 완전탐색으로 코드를 작성하다가 또다른 문제에 부딪히게 되었다.

이차원 배열을 깊은 복사를 해야한다는 문제에 생겨버린 것이다!

기본적으로 javascript는 함수에 배열을 전달하게 되면 이는 얕은 복사이므로 함수에서 배열을 수정하게 되면 원본이 훼손되는 문제가 발생했다.

1차원 배열일 경우 spread 연산자를 이용하면 쉽게 깊은 복사를 할 수 있다.

하지만, 2차원 이상일 경우 각 행은 동일한 값을 참조하고 있다.

이러한 문제를 해결하기 위해 각 행 마다 동일하게 깊은 복사를 해주어야 한다.

그래서

const newTree = tree.map(v => [...v]);

이런식으로 기존 tree라는 이름을 가진 배열의 각 행들도 깊은 복사를 해주었다.

코드 설명

우선 문제에서 주어진 배열을 linkedList 형식으로 만들어주었다.

이후 그래프를 탐색할때 좀 더 쉽게 탐색하기 위해 linkedList 형식으로 만들어주었다.

그리고 문제에서 주어진 wires 를 반복문을 통해 반복시키면서 이어진 두 전선을 끊어주어 bfs 함수를 동작시켰다.

const newTree = tree.map(v => [...v]);
const [x, y] = i;
newTree[x] = newTree[x].filter(v => v !== y);
newTree[y] = newTree[y].filter(v => v !== x);

bfs 함수코드는 아래와 같이 구현했다.

const bfs = (start, arr) => {
    const visited = new Array(n+1).fill(false);
    const queue = [arr[start].shift()];
    visited[queue[0]] = true;
    let answer = 0;
    while(queue.length){
        const v = queue.pop();
        answer += 1;
        if(!arr[v]) continue;
        for(let i of arr[v]){
            if(visited[i]) continue; 
            visited[i] = true;
            queue.push(i)
        }
    }
    return answer;
}

👩‍💻 코드

function solution(n, wires) {
    let answer = n;
    
    const tree = new Array(n+1).fill().map((_) => []);
    const startPoint = [];
    
    for(let i of wires){
        const [x, y] = i;
        tree[x].push(y);
        tree[y].push(x);
    }

    const bfs = (start, arr) => {
        const visited = new Array(n+1).fill(false);
        const queue = [arr[start].shift()];
        visited[queue[0]] = true;
        let answer = 0;
        while(queue.length){
            const v = queue.pop();
            answer += 1;
            if(!arr[v]) continue;
            for(let i of arr[v]){
                if(visited[i]) continue; 
                visited[i] = true;
                queue.push(i)
            }
        }
        return answer;
    }
    for(let i of wires){
        const newTree = tree.map(v => [...v]);
        const [x, y] = i;
        newTree[x] = newTree[x].filter(v => v !== y);
        newTree[y] = newTree[y].filter(v => v !== x);
        const a = bfs(x, newTree);
        const b = bfs(y, newTree);
        answer = Math.min(answer, Math.abs(a - b))
    }
    return answer;
}

코딩테스트 준비를 한동안 안하다가 할려니 bfs 코드, 깊은 복사 등 중요한 것을 까먹은 것 같다.

앞으로는 정리를 하면서 해당 코드가 왜 필요한지, 언제 사용하는지에 대한것을 상세히 작성해놓아야겠다.