[코딩테스트] 프로그래머스 등대 (JavaScript)

문제 설명(링크)

인천 앞바다에는 1부터 n까지 서로 다른 번호가 매겨진 등대 n개가 존재합니다. 등대와 등대 사이를 오가는 뱃길이 n-1개 존재하여, 어느 등대에서 출발해도 다른 모든 등대까지 이동할 수 있습니다. 등대 관리자 윤성이는 전력을 아끼기 위하여, 이 중 몇 개의 등대만 켜 두려고 합니다. 하지만 등대를 아무렇게나 꺼버리면, 뱃길을 오가는 배들이 위험할 수 있습니다. 한 뱃길의 양쪽 끝 등대 중 적어도 하나는 켜져 있도록 등대를 켜 두어야 합니다.

예를 들어, 아래 그림과 같이 등대 8개와 7개의 뱃길들이 있다고 합시다. 이 경우 1번 등대와 5번 등대 두 개만 켜 두어도 모든 뱃길은 양쪽 끝 등대 중 하나가 켜져 있으므로, 배들은 안전하게 운항할 수 있습니다.

등대의 개수 n과 각 뱃길이 연결된 등대의 번호를 담은 이차원 배열 lighthouse가 매개변수로 주어집니다. 윤성이가 켜 두어야 하는 등대 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

풀이

특정 위치에서 연결된 간선이 하나밖에 없다면, 해당 위치와 연결된 섬의 등대를 키는 것이 효율적이라고 생각 후 풀이

function solution(n, lighthouse) {
    const memo = new Array(n + 1).fill(false);
    let result = 0;
    
    while(lighthouse.length) {      
      const map = new Array(n + 1).fill().map(_ => []);
        
      for (const el of lighthouse) {
        const [a, b] = el;
            
        map[a].push(b);
        map[b].push(a);
      }
        
      // 탐욕법
      map.filter(el => el.length === 1).forEach((el) => {
          const [target] = el;
          if (!memo[target]) {
              memo[target] = true;
              if (map[target].length !== 1) {
                  result += 1;
              } else {
              	  // 양쪽 모두 있는 경우이므로 더하기가 두번일어난다.
                  result += 0.5;
              } 
          }
      });
        
      // 간선이 1개인 섬 모두 제거
      lighthouse = lighthouse.filter((el) => {
        const [a, b] = el;
            
        return !memo[a] && !memo[b];
      });
    }
  
    return result;
  }

결과