Portfolio

🔎 문제

school.programmers.co.kr

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

🧩 구현과정 및 코드

개인 토글 영역에 구현 과정과 코드를 자유롭게 작성해주시면 됩니다.

사용할 데이터 구조와 풀이 방향성

적용할 알고리즘 혹은 메서드

수영

구현

그래프 DFS

인접행렬

코드


// DFS, 그래프, 인접행렬
function solution(n, wires) {
    // 최대 안전 정수
    let answer = Number.MAX_SAFE_INTEGER;
    let count = 1;
    const visited = Array.from({length: n + 1}, () => false);
    const graph = Array.from({length: n + 1}, () => Array(n + 1).fill(0));
    
    for(const [v1, v2] of wires) {
        graph[v1][v2] = 1;
        graph[v2][v1] = 1;
    }
    
    function DFS(L){
        for (let i = 1; i <= n; i++) {
            if(visited[i] === false && graph[L][i] === 1) {
                visited[L] = true;
                count++;
                DFS(i);
                visited[L] = false;
            }
        }
    }
    
    for (let [v1, v2] of wires) {
        graph[v1][v2] = 0;
        graph[v2][v1] = 0;
        count = 1;
        DFS(1);
        graph[v1][v2] = 1;
        graph[v2][v1] = 1;
        answer = Math.min(answer, Math.abs(n - count - count));
    }
    return answer;
}

정은

구현

(처음 방식) wires를 돌면서 해당 연결을 끊었을 때 노드 수의 차이를 구해보려 했었다. ⇒ 구현하는게 은근 쉽지 않았던.. 다시 시도 예정 (다른 풀이) bfs로 진행. 한 원소를 제거하여 연결 끊음 ⇒ 사실 연결이 아닌 노드를 삭제한다는게 잘 이해가 안되는데, 다시 한번 볼 예정

코드


function solution(n, wires) {
    var answer = Infinity; 
    let connection = [{}];
    
    for (const wire of wires) {
        const [v1,v2] = wire;
        
        if (!connection[v1]) {
            connection[v1] = {};
        }
        if (!connection[v2]) {
            connection[v2] = {};
        }
        connection[v1][v2]=1;
        connection[v2][v1]=1;
    }
    
    for (const wire of wires) {
        const [v1,v2] = wire;
        const tree1 = new Set([v1]);
        let connectionCopy = connection;
    
        delete connectionCopy[v1].v2;
        delete connectionCopy[v2].v1;
       
        
        while (true) {
            const prevTreeSize = tree1.size;
            
            for(const leaf of tree1) {
                tree1.add(Object.keys(connectionCopy[leaf]));
                connectionCopy[leaf] = {};
            }
            
            if (tree1.size === prevTreeSize) {
                answer = Math.min(answer, tree1.size);
                break;
            }
        }
    }
    
    
    return answer;
}

종혁

구현

전선 하나를 끊는다는 의미는 wires 배열에 있는 원소 하나를 무시한다는 의미로 받아드림

wires 전체를 이용해서 그래프를 만들고 , 각 원소의 연결를 그래프에서 제거해줌

이 때 노드끼리의 연결상태가 어떻게 되는지를 조사

코드


function deepCopy(arr) {
  return arr.map(subArr => [...subArr]);
}//이중배열의 deep copy
function solution(n, wires) {
    const graph = Array.from({length : n+1},() => [])
    wires.forEach(([start,next]) => {
        graph[start].push(next)
        graph[next].push(start)
    })
   //하나를 끊는다 - wires 배열에 있는 원소 하나를 안쓰겠다는 소리
    let difference = Infinity
    wires.forEach(([start,next]) => {
        const copy = deepCopy(graph)
        //graph를 deep copy한 배열에 start-next 연결된걸 제거
        copy[start].splice(copy[start].indexOf(next),1)
        copy[next].splice(copy[next].indexOf(start),1)
        const isUsed = Array(n+1).fill(0)
        const divide = []
        for(let i=1;i<=n;i++){//전체 노드의 연결상태 조사
            if(isUsed[i]){continue}//기존에 연결되어있는걸 확인한 노드는 다시 조사 X
            isUsed[i] = 1
            divide.push(checkConnection(i,isUsed,copy))
        }
            //예시 1번) wires의 각 원소를 끊었을 때 분리된 전력망들이 가지고 있는 송전탑 개수 (+1해서 생각)
        	// [ 0, 7 ]
        	// [ 7, 0 ]
        	// [ 2, 5 ] - 절댓값 제일 작음
        	// [ 7, 0 ]
        	// [ 7, 0 ]
        	// [ 5, 2 ] - 절댓값 제일 작음
        	// [ 7, 0 ]
        	// [ 7, 0 ]
        if(divide.length === 2){//문제에서 두 전력망으로 나누었을때만 고려하라고 했음
            difference = Math.min(difference,Math.abs(divide[0] - divide[1]))
        }
        if(difference === 0){return 0}
    })

		const checkConnection = (indexNode,isUsed,copy) => {//indexNode와 연결되어있는 노드가 몇개가 있는지 조사
        let count = 0 
        const queue = [indexNode]
        while(queue.length){//index 노드부터 시작해서 - 연결되어있는 노드를 bfs 방식으로 찾기
            const curNode = queue.shift()
            for(const nextNode of copy[curNode]){
                if(isUsed[nextNode]){continue}
                queue.push(nextNode)
                isUsed[nextNode] = 1
                 count++
            }
        }
        return count+1 // indexNode와 연결되어있는 노드의 수
    }
    return difference
}

재웅

구현

간선을 잘라, 두 그룹의 노드 갯수 차이가 최소가 되는 경우

정확히 따지면 그래프 하위 구조인 트리 구조이기 때문에, 간선을 자르면 무조건 2등분됨

모든 경우를 끊어보며 최소가 되는 경우를 찾음 -> DFS

인접리스트 생성 이후 막혀 해설을 보고 분석하는 방식으로 진행하였습니다.

코드


function solution(n, wires) {
    const links = {}; 

// 인접리스트 생성
    wires.map(w => {
        const [a, b] = w;
        if(!links[a]) links[a] = [];
        if(!links[b]) links[b] = [];
        links[a].push(b);
        links[b].push(a);
    })
    
// exception을 제외한 연결 노드 수를 계산하는 함수
// DFS를 이용, 노드 간 방문처리
    const searchTree = (root, exception) => {
        let count = 0;
        const queue = [root];
        const visited = [];

        visited[root] = true;
        while(queue.length){
            const cur = queue.pop();
            links[cur].map(next => {
                if(next !== exception && !visited[next]){
                    visited[next] = true;
                    queue.push(next);
                }
            })
            count++;
        }
        return count;
    }
    
// 나올 수 있는 최대값 N-2
// wires를 순회하여 연결을 끊음
    let answer = n-2; 
    wires.map((w, i) => {
        const [a, b] = w;
        const dif = Math.abs(searchTree(a,b) - searchTree(b,a));
        answer = answer > dif ? dif : answer;
    })
    return answer;
}

✏️ 후기

문제를 풀고 느낀 점, 막혔던 부분 혹은 개선 사항 등을 자유롭게 작성해주시면 됩니다.

👧🏻

수영

최대 안전 정수를 처음 알게 됐다!

👧🏻

정은

많은 문제를 풀어서 코드 구현의 능숙도를 향상시켜야겠다.

👦🏻

종혁

유니온파인드 알고리즘을 공부해봐야겠다

👦🏻

재웅

역대급 난이도에 전의를 상실했습니다……

유니온-파인드 알고리즘을 새로 알게 되었는데, 이를 적용하여 문제를 풀어보려 합니다.

전력망을 둘로 나누기

🔎 문제

🧩 구현과정 및 코드

수영

구현

코드

정은

구현

코드

종혁

구현

코드

재웅

구현

코드

✏️ 후기