프로그래머스 등대 자바 풀이

문제 링크

문제 풀이 시간 : 2시간

문제 요약

1부터 n까지 번호가 매겨진 등대가 있고, 등대들을 잇는 뱃길이 n-1개 주어짐 (그래프는 트리)
일부 등대를 켜서 운영하려 함
모든 뱃길(간선)에 대해 해당 뱃길의 양 끝 등대 중 적어도 하나는 켜져 있어야 함
위 조건을 만족하도록 켜야 하는 등대의 최소 개수를 구하기

문제 풀이

이 문제를 처음 보고 내가 생각한 접근 방식은 아래와 같다.

리프노드와 연결된 부모 노드는 무조건 켜기

하지만 이렇게 부모노드를 다 켜고 난 후에 남은 등대들은 어떻게 처리할지에 대해서는 아무리 생각해도 방법이 떠오르지 않았다..

그래서 내가 택한 방법은 남은 등대들 중 켜진 등대와 연결되지 않은 등대와 연결된 간선의 개수가 많은 등대를 먼저 켜주면서 모든 등대를 연결시키려고 했다.

실패 코드

~~코드를 짜면서도 잘못되고 있다는걸 인지했지만..~~

결국 힌트를 참고해서 풀이 방향을 알 수 있었다.

리프노드와 연결된 부모 노드 무조건 켜기
부모노드와 연결된 노드들의 부모 노드와의 간선 제거
남은 노드들 중 다시 리프 노드 탐색 후 1,2,3 반복

이게 무슨 말이냐면 아래 사진과 같은 연결된 등대들 이 있다고 할 때,

처음에는 리프 노드인 3, 4, 7, 8, 10의 부모 노드인 1, 9, 6이 켜지게 될 것이다.

그러면 이제 1과 연결된 노드들인 2, 5, 4와의 간선을 삭제하고,

9와 연결된 간선들을 삭제하면서

새로운 리프 노드를 만들면서 같은 과정을 반복하는 것이다.

최종 코드

java

import java.util.*;

class Solution {
    public int solution(int n, int[][] lighthouse) {
        int answer = 0;
        
        List<Integer>[] arr = new ArrayList[n+1];
        for(int i=1;i<=n;i++){
            arr[i] = new ArrayList<>();
        }
        
        for(int[] now : lighthouse){
            arr[now[0]].add(now[1]);
            arr[now[1]].add(now[0]);
        }
        
        //각 노드의 차수 배열
        int[] deg = new int[n+1];
        //리프 노드 저장 큐
        Deque<Integer> q = new ArrayDeque<>();
        
        for(int i=1;i<=n;i++){
            deg[i] = arr[i].size();
            if(deg[i]==1)
                q.add(i);
        }
        
        boolean[] on = new boolean[n+1];
        
        while(!q.isEmpty()){
            int leaf = q.poll();
            //리프노드 아니라면 넘어감
            if(deg[leaf]!=1)
                continue;
            
            //부모노드 찾기
            int parent = -1;
            for(int p : arr[leaf]){
                if(deg[p]>0){
                    parent = p;
                    break;
                }
            }
            //부모 노드가 없다면 이미 연결된 상태임
            if(parent==-1){
                deg[leaf] = 0;
                continue;
            }
            
            //부모 노드가 안켜져 있다면 켜주기
            if(!on[parent]){
                on[parent] = true;
                answer++;
            }
            
            //부모 노드와 연결된 간선들 제거
            for(int nb : arr[parent]){
                if(deg[nb]>0){
                    deg[nb]--;
                    if(deg[nb]==1)
                        q.add(nb);
                }
            }
            deg[parent] = 0;
        }
        
        return answer;
    }
}

등대

문제 풀이 시간 : 2시간

문제 요약

문제 풀이

실패 코드

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기