[프로그래머스 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개가 최소가 됩니다.

 

 

 

 

 

 

 

나의 코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] lighthouse) {
        int answer = 0;
        
        Set<Integer> lightOnSet = new HashSet<>();
        
        boolean[] safety = new boolean[n+1];
        
        boolean flag = true;
        
        while(flag) {
            flag = false;
            
            ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
            
            for(int i=0; i<=n; i++) graph.add(new ArrayList<>()); 

            for(int i=0; i<lighthouse.length; i++) {
                // lightOnSet에 담겨있는 등대 번호와 연결된 것들은 넘어감
                if(lightOnSet.contains(lighthouse[i][0]) || lightOnSet.contains(lighthouse[i][1])) continue; 
                
                graph.get(lighthouse[i][0]).add(lighthouse[i][1]);
                graph.get(lighthouse[i][1]).add(lighthouse[i][0]);
            }
            
            ArrayList<Integer> leafNodeList = new ArrayList<>();
            
            for(int i=1; i<=n; i++) {
                if(graph.get(i).size() == 1) leafNodeList.add(i);
            }
            
            for(int leafNode : leafNodeList) {
                safety[leafNode] = true;
                
                if(!safety[graph.get(leafNode).get(0)]) {
                    safety[graph.get(leafNode).get(0)] = true; // 1-2-3-4-5-6인 경우 때문에 safety 배열로 불 켜진 영향권 관리 필요 
                    lightOnSet.add(graph.get(leafNode).get(0));
                    flag = true; // 불 킬 등대가 있었으므로 계속 -> 불 킬 등대가 없었으면 종료
                }
            }
        }
        
        answer = lightOnSet.size();
        
        return answer;
    }
    
}

 

풀이

1. 제일 끝에 있는 리프 노드와 연결된 노드를 불을 키고 해당 노드를 Set에 담은 후에 불을 킨 노드까지를 제외하고 다시 그래프를 만들어 불을 킨 노드와 연결된 노드가 리프 노드가 되도록 만든다. 다시 리프 노드와 연결된 노드를 불을 키고 반복한다. 다만, 리프 노드와 연결된 노드를 불을 킴으로써 안전한 영향권이 바뀌기 때문에 안전한 영향권을 관리 하기 위해 배열을 만들어 안전한 영향권을 관리하면서 진행한다.  
2. 안전한 뱃길을 관리하기 위한 safety와 불을 켠 등대를 담을 Set을 생성한다.
3. 이제 boolean형 변수 flag를 true로 초기화 하고 만들고 flag가 true이면 반복하는 while문을 생성한다.
4. while문에 들어서면 우선 flag를 false로 변경하고 그래프를 생성하기 위해 ArrayList를 선언타입으로 하는 ArrayList인 graph를 생성한다.
5. 등대의 연결 상태를 나타내는 주어진 lighthouse를 for문을 돌면서 lighthouse[i]가 Set에 담겨있지 않다면 각 등대 번호의 인덱스에 연결 등대를 graph에 담도록 한다.
6. 이제 그래프에서 끝에 있는 등대(리프 노드)를 담기 위해 사용할 ArrayList인 leafNodeList를 생성한다.
7. graph를 for문을 돌면서 만약 해당 등대 번호 인덱스의 ArrayList 크기가 1이라면 연결된 등대가 1개 뿐인 것이므로 리프 노드로 여기고 leafNodeList에 담는다.
8. leafNodeList를 for each문을 돌면서 safety의 해당 leafNode에 해당하는 인덱스를 true로 변경한다.(leafNode에 해당하는 등대를 안전한 뱃길로 변경)
9. 그리고 끝에 있는 등대(리프 노드)와 연결된 등대가 safety가 false라면 해당 등대를 불을 키고(Set에 담고) safety[해당 등대]를 true로 변경하고 flag를 true로 변경한다. (flag를 true로 변경하는 것은 이번 턴에 불을 킨 등대가 있었으므로 다시 while문을 돌면서 불을 킬 등대가 있는지 확인하는 것이다. 이번 턴에 불을 킨 등대가 없었으면 flag가 그대로 false이므로 while문이 종료된다)
10. 따라서 while문의 다음 턴에는 graph를 만들 때 불을 켠 등대가 포함되는 것은 제외(리프노드와 리프노드와 연결된 방금 불을 켠 등대를 제외)하므로 불을 켠 등대와 연결된 바로 다음 노드들이 리프 노드가 되어 다시 진행하는 것이다.
11. 예를 들어 등대가 1-2-3-4-5-6 이라고 할 때 살펴보자.
    1. 처음에 그래프는 1-2-3-4-5-6이 되고 리프 노드는 1, 6이 되고 safety[1]과 safety[6]이 true가 된다.
    2. 그리고 각 리프 노드와 연결된 2와 5가 불이 켜지고 Set에 담긴다.(flag = true로 변경)
    3. flag가 true이기 때문에 다시 그래프를 만들면 2와 5가 포함된 연결은 만들지 않으므로 1-2, 2-3, 4-5, 5-6은 만들지 않기 때문에 3-4가 되고 리프 노드는 담으면 3, 4가 된다.
    4. 이제 리프 노드를 3부터 확인하면서 safety[3]을 true로 변경하고 3과 연결된 4의 safety[4]가 아직 false이므로 safety[4]를 true로 변경하고 4의 불을 켜고 Set에 담는다.(flag = true로 변경) 그리고 다음 리프 노드인 4를 확인해보면 safety[4]를 다시 true로 변경하고 4와 연결된 3의 safety[3]이 이미 true이기 때문에 넘어가게 된다.(이러한 경우 때문에 safety 배열로 안정권 관리가 필요)
    5. flag가 true이기 때문에 다시 그래프를 만들면 2, 4, 5가 포함된 연결은 만들지 않으므로 그래프에는 아무것도 담기지 않게 된다. 따라서 아무것도 나머지도 진행할 것이 없으므로 flag는 그대로 false가 되어 while문이 종료된다.
    6. 따라서 최종적으로 최소로 불을 켠 등대는 총 3개가 된다.