등대 (프로그래머스) JAVA

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

프로그래머스

문제 설명

한 줄로 축약해서 어느 등대에 촛불을 켜야 모든 뱃길에 불을 밝힐 수 있는지 찾는 프로그램을 만드는 것입니다.

1에 키면 2,3,4에 다 불을 킬 수 있고 5에 키면 6,7,8에 불을 킬 수 있어 결국 모든 곳에 불을 킬 수 있습니다.

 

문제에 대한 아이디어

이 문제를 보면 n개인 노드에서 간선이 n-1개이고 모든 등대까지 갈 수 있는 길이 모두 주어진다 했으므로 모든 노드가 연결되어 있음을 알 수 있습니다.

이런 문제는 보통 트리를 바꿔서 풀면 쉽게 풀 수 있습니다. 위의 예제를 1이 루트인 트리로 바꿔 보겠습니다.

이제 모든 곳에 불을 밝히기 위해서는 1번과 5번에 불을 켜야 하는게 더 확실하게 보입니다.

• 리프 노드에서 부터 올라오면서 리프노드의 부모 노드일 경우 불을 킵니다.
• 불을 킨 노드의 바로 위 노드는 불을 안켜도 됩니다.

리프 노드인 6,7,8의 부모 노드인 5번에 불을 킵니다. 리프노드의 노드인 2,3,4의 불을 킵니다.

 

 

전체 코드

import java.util.*;

class Solution {
    static ArrayList<Integer> graphs[]; // 그래프
    static boolean visited[]; // 방문 체크
    static boolean rights[];  // 불이 켜져 있는지 체크
    static int parent[];  // 자신의 부모 노드를 메모리
    static int answer = 0;
    public int solution(int n, int[][] lighthouse) {
        graphs = new ArrayList[n+1];
        visited = new boolean[n+1];
        rights = new boolean[n+1];
        parent = new int[n+1];
        for(int i = 1; i <= n; ++i){
            graphs[i] = new ArrayList<>();
        }
        for(int i = 0; i < lighthouse.length; ++i){
            graphs[lighthouse[i][0]].add(lighthouse[i][1]);
            graphs[lighthouse[i][1]].add(lighthouse[i][0]);
        }
        
        // 부모 노드를 알기 위한 BFS 탐색
        Deque<Integer> dq = new ArrayDeque<>();
        dq.add(1);
        visited[1] = true;
        while(!dq.isEmpty()){
            int now = dq.removeFirst();
            for(int i = 0; i < graphs[now].size(); ++i){
                int next = graphs[now].get(i);
                if(visited[next]) continue;
                visited[next] = true;
                parent[next] = now;
                dq.add(next);
            }
        }
        
        // 리프 노드 부터 체크 하기위한 DFS 탐색
        visited = new boolean[n+1];
        visited[1] = true;
        dfs(1);
        return answer;
    }
    
    public void dfs(int now){
        boolean ch = true;
        
        // 자신의 자식들을 모두 탐색
        for(int i = 0; i < graphs[now].size(); ++i){
          int next = graphs[now].get(i);
          if(visited[next]) continue;
          visited[next] = true;
          dfs(next);
        }
   
        // 현재 자신의 자식이 다 불을 켜져 있으면 자신은 안 켜줘도 된다.
        for(int i = 0; i < graphs[now].size(); ++i){
          int next = graphs[now].get(i);
          if(!rights[next]) ch = false; 
        }
        if(ch) return;
        
        // 자신이 불이 켜져 있으면 넘어간다.
        if(rights[now] == true) return;
        
        // 자신이 불도 안켜져 있고 자신의 부모가 불이 안켜져 있으면 부모의 불을 킨다.
        if(rights[parent[now]] == false){
            ++answer;
            rights[parent[now]] = true;
        }   
    }
}

https://github.com/SeWooooong/CodingTest_Practice/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/3/133500.%E2%80%85%EB%93%B1%EB%8C%80