[Level 3] 등대 - Java

https://school.programmers.co.kr/learn/courses/30/lessons/133500

프로그래머스

문제 설명

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

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

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

---

제한사항

• 2 ≤ n ≤ 100,000
• lighthouse의 길이 = n – 1
  • lighthouse 배열의 각 행 [a, b]는 a번 등대와 b번 등대가 뱃길로 연결되어 있다는 의미입니다.
    • 1 ≤ a ≠ b ≤ n
    • 모든 등대는 서로 다른 등대로 이동할 수 있는 뱃길이 존재하도록 입력이 주어집니다.

---

입출력 예

n	lighthouse	result
8	[[1, 2], [1, 3], [1, 4], [1, 5], [5, 6], [5, 7], [5, 8]]	2
10	[[4, 1], [5, 1], [5, 6], [7, 6], [1, 2], [1, 3], [6, 8], [2, 9], [9, 10]]	3

---

입출력 예 설명

입출력 예 #1

• 본문에서 설명한 예시입니다.

입출력 예 #2

• 뱃길은 아래 그림과 같이 연결되어 있습니다. 윤성이가 이중 1, 6, 9번 등대 3개만 켜 두어도 모든 뱃길은 양쪽 끝 등대 중 하나가 켜져 있게 되고, 이때의 등대 개수 3개가 최소가 됩니다.

 

 

 

 

 

문제 솔루션

DFS 를 통한 완전탐색
등대들을 `1`이 루트노드인 트리라고 생각해보자. 

이렇게 변경하고 나면, 어느 등대를 켤지 조금 더 잘 보인다.
리프노드가 최대한 많이 연결된 등대들을 밝히는 것이 유리하다는 것을 볼 수 있다.
 
따라서, 등대를 켜는 조건은 다음과 같다.
현재 등대의 자식 중 하나라도 꺼져있는 경우, 현재 등대의 불을 켠다. ( = 자식노드들이 모두 켜져있다면, 현재 등대는 키지 않아도 된다.)
 
시간복잡도
1. 인접리스트를 만드는 과정 : O(N)
2. DFS : O(V + E) = O (N + N - 1) = O(N)
 
총 시간복잡도: O(N)

 

전체 코드 

import java.util.*;

class Solution {
    public int solution(int n, int[][] edges) {
        boolean[] lights = new boolean[n + 1];
        boolean[] visited = new boolean[n + 1];
        List<Integer>[] graphs = new ArrayList[n + 1];
        
        lights[0] = false;
        visited[1] = true;
        
        // 인접리스트 graphs 생성
        for (int i = 1; i <= n; i++) {
            graphs[i] = new ArrayList<>();
        }
        
        for (int[] edge: edges) {
            graphs[edge[0]].add(edge[1]);
            graphs[edge[1]].add(edge[0]);
        }
       
        turnLight(1, 1, graphs, lights, visited);
        
        int count = 0;
        for (boolean lightOn: lights) {
            if (lightOn) count++;
        }
        
        return count;
    }
    
    // dfs 알고리즘 적용
    public void turnLight(int curr, int parent, 
    	List<Integer>[] graphs, boolean[] lights, boolean[] visited
    ) {
        // 무 방향 인접리스트 이므로, parent 가 포함되어 있다.
        // visited 로 체크 가능
        for (int vertex: graphs[curr]) {
            if (!visited[vertex]) {
                visited[vertex] = true;
                turnLight(vertex, curr, graphs, lights, visited);    
            }
        }
        
        // 부모들 제외한 자식 노드에 대해서 체크
        // 리프노드인 경우에는 lights 를 키지 않는 것으로 처리
        boolean hasAnyChildOff = false;
        for (int vertex: graphs[curr]) {
            if (vertex == parent) continue;
            if (!lights[vertex]) {
                hasAnyChildOff = true;
                break;
            }
        }
        
        if (hasAnyChildOff) {
            lights[curr] = true;
        }
    }
}