레벨 3 – 등대

by

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/133500

여자 같은

운동을 포함해야 하는 세트를 선택하십시오. 취소 확인

'추천 관련글,

softeer.ai



문제에 대한 이해


이 문제를 이해하는 가장 쉬운 방법은 문제에서 위의 그림을 보는 것입니다.


등대는 기본적으로 밤에 길을 밝혀주는 등대이며 모든 수로에는 밤에 선박을 운항할 때 위험을 피하기 위해 등대가 켜져 있어야 합니다.


문제에서 그들은 전기 절약을 이유로 최소한의 등대만 켜고자 한다.

위의 정보를 통해 최소한의 등대만 켜두는 것이 좋지만 끄는 것은 야간 운전 시 위험할 수 있다는 점을 이해했다면 등대가 몇 개나 필요한지 파악하는 문제입니다.

솔루션 프로세스 및 사고 프로세스

이 문제를 풀면서 가장 먼저 떠오른 것은
“최소한의 등대로 이 모든 수로를 비추려면 등대 수를 계산하기 위한 일정한 공식이 있어야 합니다.

”라고 생각했습니다.


문제를 자세히 이해하기 전에 그림을 보십시오.
“아, BFS/DFS와 현재 진행 중인 관계를 조건으로 따져보면 정답이 나올까?”
이 흐름에 따라 논리를 검토한 결과 문제가 있음을 깨달았습니다.


탐색할 대상이 없기 때문에 루프를 벗어날 지점을 찾기도 어렵고, 이런 식으로 개별적으로 탐색하기에는 너무 많은 경우가 있다고 생각했습니다.

그래서 다른 방법으로 문제를 풀려고 했고 당시 떠오른 논리는 다음과 같다.


“다른 등대로 연결되는 수로가 하나뿐인 등대는 자체 등대 또는 연결된 등대와 연결되는 유일한 수로가 있어야 합니다.

그것은 그것으로 이어지는 모든 수로를 밝힐 수 있습니다.

”
따라서 “다른 등대와 연결된 단일 수로 등대”가 자체 등대를 켜지 않고 “다른 등대와 연결된 여러 개의 수로 등대”가 켜지면 켜야 할 등대의 수를 줄일 수 있습니다.

실습에서 주어진 예를 고려하면,


위 이미지의 경우에도 다른 등대와 연결된 수로 중 하나인 10, 3, 8, 7, 4번은 켜져 있지 않았고, 연결된 1, 6, 9번 등대가 켜져 있을 때는 모든 수로가 켜져 있다는 것입니다.

.
이를 이용하여 다음과 같은 흐름으로 코드를 작성하였다.

  1. “다른 등대와 연결된 수로가 하나뿐인 등대”에 연결된 등대를 켭니다.

  2. 이 등대와 관련된 모든 등대가 켜져 있는지 확인하십시오.
  3. 불이 들어오지 않는 등대를 확인하십시오.
  4. 이러한 등대만 포함하는 배열을 사용하여 1단계에서 반복적으로 확인합니다.

이 흐름으로 문제를 해결했고 해결 방법은 다음과 같습니다.

암호

import java.util.*;
import java.io.*;

class Solution {
    public int solution(int n, int()() lighthouse) {
        int answer = 0;
        
        //다른 등대와 연결되는 길이 하나뿐인 등대를 확인하는 HashSet
        //중복을 방지하기 위해 HashSet 사용
        HashSet<Integer> edge = new HashSet<Integer>();
        //중심이 되는, 반드시 켜야하는 등대를 확인하는 HashSet
        HashSet<Integer> onList = new HashSet<Integer>();
        
        for (int num = 0; num < n; num++){
            int() cnt = new int(n+1);
            //아직 밝혀지지 않은 등대의 수를 확인하는 변수
            int remainsCnt = 0;
            //아직 밝혀지지 않은 등대를 확인하는 배열
            int()() remainsList = new int(lighthouse.length)(2);
        
        	//각 뱃길의 정보를 확인하며 등대와 연결된 뱃길의 수를 확인
            for (int i = 0; i < lighthouse.length; i++){
                cnt(lighthouse(i)(0))++;
                cnt(lighthouse(i)(1))++;
            }
        
        	//위에서 확인한 연결된 뱃길의 수가 1개일 경우를 확인함
            for (int i = 0; i < cnt.length; i++){
                if (cnt(i) == 1){
                    edge.add(i);
                }
            }
            
            //위에서 확인한 연결된 뱃길의 수가 1개인 정보를 통해
            //반드시 켜야하는 등대를 확인
            for (int i = 0; i < lighthouse.length; i++){
                if (edge.contains(lighthouse(i)(0))){
                    onList.add(lighthouse(i)(1));
                }
                else if (edge.contains(lighthouse(i)(1))){
                    onList.add(lighthouse(i)(0));
                }
            }
            
        
        	//반드시 켜야하는 등대를 기준으로 모든 뱃길을 확인하여 아직 안 켜진 등대를 확인
            for (int i = 0; i < lighthouse.length; i++){
                if (!
onList.contains(lighthouse(i)(0)) && !
onList.contains(lighthouse(i)(1))){
                    remainsList(remainsCnt) = lighthouse(i);
                    remainsCnt++;
                }
            }
        
        	//모든 뱃길이 전부 밝혀졌다면 반복문 탈출
            if (remainsCnt == 0){
                break;
            }
            
            //하나가 남았다면, 그 뱃길의 어느쪽 등대를 켜도 그 뱃길은 밝혀지므로
            //값을 1 추가하고 반복문 탈출
            else if (remainsCnt == 1){
                answer += 1;
                break;
            }
            
            //두 개 이상이 남았다면, 남은 뱃길 정보만 다시 담고 반복문 처음부터 같은 과정을 반복함
            else{
                lighthouse = new int(remainsCnt)(2);
                for (int i = 0; i < remainsCnt; i++){
                    lighthouse(i) = remainsList(i);
                }
            }
        }
        
        answer += onList.size();
        return answer;
    }
}