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

 

 

---

나의 풀이 

 

풀이 1은  한쪽 전선의 개수를 구했다. (아직 미해결)

왜냐하면 전선 개수 + 1 = 송전탑 개수가 되기 때문이다. 

 

풀이 2는 송전탑의 개수를 구해서 문제를 풀었다. 

 

풀이 1

틀린 풀이

function solution(n, wires) {
    wires.sort(([a,_], [b,__]) => a-b)

    let answer = n
    
    function tracking(n, wires, wireCopy, index) {
        if(index + 1 > wires.length) return
        wireCopy.splice(index, 1)
        const firstLine = wireCopy.reduce((acc, cur,i) => {
            if(i === 0){
              acc.push(cur)
                return acc
            } 
           if(acc.find(x => x.includes(cur[0]) || x.includes(cur[1]))) {
              acc.push(cur)
              }
            return acc 
        },[])
        answer = Math.min(answer, Math.abs(n - 2*(firstLine.length+1)))
        tracking(n, wires, [...wires], index+1)
    }
    tracking(n,wires, [...wires], 0)
    return answer
}

1. wire를 index에 따라 하나씩 자르고 원상복구하고 다시 자르고 원상복구하기 위해 복사를 한다. 

2. firstLine에는 연결되어 있는 것만 push해준다 즉  firstLine만 구해주면 secondLine = n-(firstLine+1)  이다 

쉽게말해 전선을 하나 끊으면 자동으로 양분이 되기에 한쪽 송전탑 개수만 구해주면 된다. 

3. 따라서 tracking 함수를 실행하면 모든 전선을 한 번 자르고 최소가 되는 절대값을 answer에 저장해준다. 

 

하지만 13개중에 7개가 틀리다.  아직 왜 틀리는지 반례가 무엇인지 모른다. 

 

추가 테스트 케이스

모두 1<= v1 < v2 <= n 을 만족한다. 

 

---

 

풀이 2

 

이 풀이는 다른 분 풀이를 많이 참고했다. 

function solution(n, wires) {
  // n은 100이하 자연수
  let answer = 100;

  // 모든 경우 확인
  for (let i = 0; i < wires.length; i++) {
    // 2개로 분할 할  것 중에 첫 번째
    const firstLine = new Set();
    const sliceWires = [...wires];

    let isLine = true;

    // wires 하나씩 끊기
    sliceWires.splice(i, 1);

    const firstWire = sliceWires.pop();

    // 첫 번째 line에 넣기
    firstLine.add(firstWire[0]);
    firstLine.add(firstWire[1]);

    while (isLine) {
      isLine = false;

      for (let index = 0; index < sliceWires.length; index++) {
        const currWire = sliceWires[index];
        // wire가 연결되었을 때
        if (firstLine.has(currWire[0]) || firstLine.has(currWire[1])) {
          // firstLine으로 이동
          sliceWires.splice(index, 1);
          firstLine.add(currWire[0]);
          firstLine.add(currWire[1]);

          // 전선이 순서대로 있지 않을 수 있기 때문에
          isLine = true;
        }
      }
    }

    const secondLineLength = n - firstLine.size;

    // 두 개의 차이가 최소가 되도록
    answer = Math.min(answer, Math.abs(firstLine.size - secondLineLength));
  }

  return answer;
}

송전탑이 전선으로 연결되어있으면 firstLine.add 를 해주었다.  

이렇게 하면 n-firstLine.size 는 자동으로 secondLineLength가 된다. 

 

 

 

---