[프로그래머스] 등대

문제

코딩테스트 연습 - 등대

알고리즘 문제 연습 카카오톡 친구해요! 프로그래머스 교육 카카오 채널을 만들었어요. 여기를 눌러, 친구 추가를 해주세요. 신규 교육 과정 소식은 물론 다양한 이벤트 소식을 가장 먼저 알려드립니다.

school.programmers.co.kr

문제 정리

요약

• n개의 등대와 n-1개의 뱃길이 존재합니다.
• 어느 등에서 출발해도 다른 모든 등대까지 이동할 수 있습니다.
• 한 뱃길의 양쪽 끝 등대 중 적어도 하나는 커져 있어야 합니다.
• 이때 켜 두어야 하는 등대 개수의 최솟값을 구해야합니다.

입력 조건

• n : 2 ~ 100,000
• lighthouse[] : n - 1
• lighthouse 배열의 각 행 [a, b]는 a번 등대와 b번 등대 사이에 뱃길이 있음을 의미합니다.

출력

켜 두어야 하는 등대 최소 개수 반환.

---

문제 풀이

아이디어

그래프 관점에서 등대를 정점, 뱃길을 간선으로 보면 정점은 n개이고 간선이 n - 1개이며 모든 정점이 연결되어 있으므로 주어진 그래프는 트리 구조임을 알 수 있습니다.

이 문제의 핵심은 리프 노드는 선택할 필요가 없다입니다.

리프 노드를 선택할 때 오직 하나의 간선만 커버할 수 있습니다. 반면에 부모 노드를 선택하여 해당 간선뿐만 아니라 부모와 연결된 다른 간선들도 함께 커버할 수 있습니다. 즉, 부모 노드를 선택하는 것이 항상 동일하거나 더 많은 간선을 커버할 수 있습니다.

어떤 최적해에서 리프 노드가 선택되어 있다고 가정할 때 해당 리프 노드를 제거하고 부모 노드를 선택해도, 커버되는 간선 수는 유지되고 선택된 노드 수는 증가하지 않습니다. 따라서 항상 리프 대신 부모 노드를 선택하는 형태로 최적해를 변환할 수 있습니다.

이러한 성질을 이용하여 트리에서 리프부터 위로 올라가며 선택을 결정하는 Greedy 전략을 사용하여 해결할 수 있습니다.

알고리즘 흐름

1. 리프 노드를 초기화합니다.
   • 각 정점의 degree를 계산한 뒤, degree == 1인 정점을 리프로 정의합니다.
   • 이 리프들을 큐(또는 스택)에 넣어 초기 상태를 구성합니다.
2. 리프를 하나씩 처리합니다.
   • 큐에서 리프 노드를 꺼내고, 해당 리프와 연결된 부모 노드를 확인합니다.
   • 아직 선택되지 않은 부모 노드라면, 해당 부모 노드를 선택합니다.
3. 간선을 제거하고 상태를 갱신합니다.
   • 선택된 부모 노드와 연결된 모든 간선을 제거합니다.
   • 이 과정에서 인접 노드들의 degree를 감소시킵니다.
4. 새로운 리프를 큐에 추가합니다.
   • 간선 제거로 인해 degree == 1이 된 노드를 새로운 리프로 간주하고 큐에 추가합니다.
5. 큐가 빌 때까지 2번부터 반복합니다.

이때 모든 간선을 한 번씩만 처리하므로 O(n)의 시간 복잡도를 가집니다.

---

풀이 코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] lighthouse) {
        // 인접 리스트
        ArrayList<HashSet<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjList.add(new HashSet<>());
        }

        // 각 노드의 차수
        int[] degree = new int[n];

        // 인접 리스트 및 차수 계산
        for (int[] edge : lighthouse) {
            int u = edge[0] - 1, v = edge[1] - 1;
            adjList.get(u).add(v);
            adjList.get(v).add(u);
            degree[u]++;
            degree[v]++;
        }

        // 리프 노드(차수 1인 노드) 찾기
        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            if (degree[i] == 1) {
                queue.offer(i);
            }
        }

        // greedy으로 부모 노드 선택.
        int answer = 0;
        boolean[] visited = new boolean[n];

        while (!queue.isEmpty()) {
            int leaf = queue.poll();

            if (visited[leaf]) continue;

            visited[leaf] = true;

            for (int parent : adjList.get(leaf)) {
                if (visited[parent]) continue;

                // 부모 노드 선택
                answer++;
                visited[parent] = true;

                for (int next : adjList.get(parent)) {
                    // 부모 노드와 연결된 간선 제거
                    degree[next]--;

                    // 부모 노드와 연결된 노드 중에서 방문하지 않고
                    // 차수가 1인 노드(리프 노드) 선택.
                    if (!visited[next] && degree[next] == 1) {
                        queue.offer(next);
                    }
                }
            }
        }

        return answer;
    }
}

---

Minimum Vertex Cover 관점

등대 문제를 다음과 같이 재해석 할 수 있습니다.

모든 간선을 커버(한쪽 끝점이 선택되도록 포함)하기 위해 최소한의 노드를 선택하는 문제

이는 그래프 이론에서 말하는 Minimum Vertex Cover 문제 입니다. NP-hard 문제이지만, 트리 구조에서는 효율적으로 해결 할 수 있으며 대표적으로 DP와 Greedy 두 가지 접근이 존재합니다.

DP 풀이이 아이디어는 아래 글을 참고하면 좋겠습니다.

• MVC in tree with DP