프로그래머스 lv.2 전력망을 둘로 나누기

 

 

문제 보기

 

DFS/BFS 문제는 지도 형식으로 주어진 문제만 풀어봐서 이 문제처럼 인접 리스트로 주어진 문제가 낯설었다.

이 문제를 기회로 인접 리스트에 대해서도 알게 되고 인접 행렬도 구현해 볼 수 있어서 아주 유익했다.

 

DFS 풀이

/* 인접 행렬 이용한 방법 */
function solution(n, wires) {
    const graph = Array.from({length: n + 1}, () => Array(n + 1).fill(0))
    const dfs = (arr, node) => {
        let res = 0
        for (let i = 1; i <= arr[node].length; i += 1) {
            if (arr[node][i]) { // 연결되어 있다면 방문 처리
                arr[node][i] = arr[i][node] = 0
                res += 1 + dfs(arr, i)
            } 
        }
        return res
    }
    let result = 100
    
    // 와이어 연결 정보 저장(인접 행렬 만들기)
    wires.forEach(wire => {
        graph[wire[0]][wire[1]] = graph[wire[1]][wire[0]] = 1
    })
    // 와이어를 하나씩 끊고 끊어진 각 노드 2개에 대하여 DFS수행 후의 차이를 계산
    wires.forEach(wire => {
        const copy = graph.map(v => v.slice());
        const [a, b] = wire
        copy[a][b] = copy[b][a] = 0
        result = Math.min(result, Math.abs(dfs(copy, a) - dfs(copy, b)))
    })
    return result
}

 

BFS 풀이(출처 : https://highero.tistory.com/61)

function solution(n, wires) {
    wires = wires.sort(); // 테스트케이스 7번
    let answer = 1e9;
    for (let i=1; i<wires.length; i++) {
        // 방문 배열 생성
        const visited = Array(n+1).fill(0);
        // 배열을 하나씩 삭제해서 wires.length-1만큼 만들기
        const temp = wires.slice(0,i-1).concat(wires.slice(i));
        // 송전탑 그래프 만들기
        const towers = Array.from({length: n+1}, ()=>[]);
        for (const [a, b] of temp) {
            towers[a].push(b);
            towers[b].push(a);
        }
        // bfs, 정점의 수 세기 (방문한 정점 체크)
        const bfs = (n) => {
            const q = [n];
            visited[n] = 1;
            let cnt = 1;

            while (q.length) {
                const cur = q.shift();
                for (const next of towers[cur]) {
                    if (!visited[next]) {
                        q.push(next);
                        visited[next] = 1;
                        cnt++;
                    }
                }
            }
            return cnt;
        }
        // 하나를 잘랐기 때문에 정점의 수는 두개가 나옴
        const doubleCnt = [];
        for (let i=1; i<=n; i++) {
            if (!visited[i]) doubleCnt.push(bfs(i));
        }
        // 두개의 차의 절댓값과 answer를 비교해서 최솟값 구하기
        answer = Math.min(answer, Math.abs(doubleCnt[0]-doubleCnt[1]));
    }
    
    return answer;
}