프로그래머스 | 할인 행사

📍문제 설명📍

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

---

📚입출력 예시📚

4번과 7번을 연결하는 전선을 끊으면 두 전력망은 각 6개와 3개의 송전탑을 가지며, 이보다 더 비슷한 개수로 전력망을 나눌 수 없습니다.
또 다른 방법으로는 3번과 4번을 연결하는 전선을 끊어도 최선의 정답을 도출할 수 있습니다.

---

💯성공한 풀이💯

function solution(n, wires) {
    // 트리 돌면서 간선 하나씩 끊고 그때의 최소값 
    let answer = Infinity;
    const tree = Array.from(Array(n + 1), () => []);

    wires.map((w) => {
        let [a, b] = w;
        tree[a].push(b);
        tree[b].push(a);
    });
    
    console.log(tree);
    
    const bfs = (root, other) => {
        const visited = Array.from({length: n + 1}, () => false);
        let count = 0;
        let queue = [root];
        console.log(queue)
        visited[root] = true;
        
        while(queue.length) {
            let cur = queue.pop();
            
            tree[cur].forEach((item) => {
                if(item !== other && visited[item] === false) {
                    visited[item] = true;
                    queue.push(item);
                }
            });
            
            count++;
        }
        return count;
    }
    
    wires.forEach(w => {
        let [a, b] = w;
        // 노드간 연결 끊기
        answer = Math.min(answer, Math.abs(bfs(a, b) - bfs(b, a)));
    });
    
    return answer;
}

💡문제 접근 방식💡

문제에서 트리라는 단어가 주어졌으니, 트리로 접근해야한다.

const tree = Array.from(Array(n + 1), () => []);

wires.map((w) => {
  let [a, b] = w;
  tree[a].push(b);
  tree[b].push(a);
});

우선 트리를 초기화 해준다.
tree[a].push(b);
tree[b].push(a);
위 두줄의 코드로 노드가 어떻게 연결되어있는지 넣어준다.

const bfs = (root, other) => {
  const visited = Array.from({length: n + 1}, () => false);
  let count = 0;
  let queue = [root];
  visited[root] = true;
  	while(queue.length) {
      let cur = queue.pop();
      tree[cur].forEach((item) => {
        if(item !== other && visited[item] === false) {
          visited[item] = true;
          queue.push(item);
         	}
        });
        count++;
    }
        return count;
}

bfs를 통해 완전 탐색을 한다.
지금의 상황은 root와 other가 연결이 끊긴 상황을 가정하고 bfs를 돈다고 생각하는것이다.
그래서 root와 연결된 노드만 bfs를 돌아준다.

wires.forEach(w => {
        let [a, b] = w;
        // 노드간 연결 끊기
        answer = Math.min(answer, Math.abs(bfs(a, b) - bfs(b, a)));
    });

위 코드로 두 전력망의 차이를 계산하여 최소값을 return 해준다.

2일에 걸쳐서 이 문제를 풀었다.
트리와 bfs를 섞어서 나온 문제라 쉽지는 않았지만, 재미있었던 문제였다.