[Programmers / JS] 86971번 - 전력망을 둘로 나누기

Problem

문제 보기

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

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

---

Solution

function solution(n, wires) {
    //전선을 끊었을 때 두 전력망이 갖게 되는 송전탑 제일 적은 개수 차이 return
    const line = {};
    
    //각 송전탑 전선 연결
    wires.forEach((it) => {
        if(line.hasOwnProperty(it[0])) {
            line[it[0]].push(it[1]);
        } else {
            line[it[0]] = [it[1]];
        }
        
        if(line.hasOwnProperty(it[1])) {
            line[it[1]].push(it[0]);
        } else {
            line[it[1]] = [it[0]];
        }
    });
    
    //모든 송전탑
    let allWires = [];
    
    for (const key in line) {
        allWires.push(key)
    }
    
    let answer = [];
    let sum = 0;
    
    const lineCount = (target, count) => {
        //target과 연결된 다른 송전탑(count)에서 지금 연결된 송전탑(target) 제외
        let lineLength = line[count].filter((x) => x !== Number(target));
        
        //target 제외하고도 연결된 다른 송전탑이 존재한다면 sum에 개수 추가
        if(lineLength.length) {
            lineLength.forEach((it) => {
                sum += lineCount(count, it);
            })
        }
        return lineLength.length;
    }
    
    //모든 경우의 수 송전탑을 차례대로 끊었을 경우 찾기
    allWires.forEach((it) => {
        line[it].forEach((x)=> {
            //it : 송전탑 x : 해당 송전탑에 연결된 다른 송전탑
            let cut = lineCount(it, x) + sum + 1;
            answer.push(Math.abs(n - cut - cut));
            sum = 0;
        });
    });
    
    return Math.min(...answer);
}

기존 위의 코드는 테스트코드는 모두 통과하나 제출했을 때 통과하지 못한다ㅜㅜ
무슨 반례가 있을까 고민해봤는데 찾아본 웬만한 반례들은 다 통과를 해서 어느 반례때문에 통과하지 못하는지를 알 수 없다..

아래는 다시 수정한 코드

const createLine = (wires) => {
  const line = {};

  wires.forEach(([from, to]) => {
    if (line.hasOwnProperty(from)) {
      line[from].push(to);
    } else {
      line[from] = [to];
    }

    if (line.hasOwnProperty(to)) {
      line[to].push(from);
    } else {
      line[to] = [from];
    }
  });

  return line;
}

const towerCount = (source, target, line, n) => {
  const visited = [];
  const queue = [source];
  visited[source] = true;
  let count = 1;

  while(true) {
    if (queue.length === 0) {
      return count;
    }

    const current = queue.shift();
    line[current]
      .filter((it) => it !== target)
      .filter((it) => !visited[it])
      .forEach((it) =>{
        queue.push(it);
        count++;
        visited[it] = true;
      });
  }
};

function solution(n, wires) {
  const line = createLine(wires);

  let answer = [];

  Array.from({ length: n }, (_, index) => index + 1)
    .forEach((tower) => {
      line[tower].forEach((it) => {
        const count = towerCount(tower, it, line, n);
        answer.push(Math.abs((n - count) - count));
      });
    });

  return Math.min(...answer);
}

---

function solution(n, wires) {
  const line = createLine(wires);

  let answer = [];

  Array.from({ length: n }, (_, index) => index + 1)
    .forEach((tower) => {
      line[tower].forEach((it) => {
        const count = towerCount(tower, it, line, n);
        answer.push(Math.abs((n - count) - count));
      });
    });

  return Math.min(...answer);
}

const createLine = (wires) => {
  const line = {};

  wires.forEach(([from, to]) => {
    if (line.hasOwnProperty(from)) {
      line[from].push(to);
    } else {
      line[from] = [to];
    }

    if (line.hasOwnProperty(to)) {
      line[to].push(from);
    } else {
      line[to] = [from];
    }
  });

  return line;
}

createLine은 각 전력망을 다 연결해준다.
예를 들어

 

위와 같은 사진의 경우
1 : [3]
3 : [1, 4, 2]
2 : [3]
... 과 같이 전력망들이 연결되어있다.

//차례대로, 연결된 송전탑, 모든 송전탑, 송전탑 개수
const towerCount = (source, target, line, n) => {
  const visited = [];
  const queue = [source];
  visited[source] = true;
  let count = 1;

  while(true) {
    if (queue.length === 0) {
      return count;
    }

    const current = queue.shift();
      
    line[current]
      .filter((it) => it !== target)
      .filter((it) => !visited[it])
      .forEach((it) =>{
        queue.push(it);
        count++;
        visited[it] = true;
      });
  }
};

모든 전력망을 돌면서 모든 경우의 수를 계산해준다.
현재의 송전탑과 연결된 송전탑 중 끊으려는 송전탑과 방문했던 송전탑을 제외한 송전탑 개수 count를 한다.