등대 [Lv. 3] (C++)

프로그래머스

인천 앞바다에 1 ~ N까지의 번호를 가진 N개의 등대가 존재합니다.

야간에는 등대에 불을 켜두어야하는데 하나의 등대에 불을 키면 근처의 등대에는 불을 킬 필요가 없습니다.

전력을 아끼기위해 최소한의 등대에만 불을 킨다고 할 때 몇개의 등대에 불을 키면 되는지 찾아주세요

 

풀이 방법

불을 키는 등대의 조건은 근처에 가장 많은 등대가 있을 때라고 생각할 수 있습니다. (영향력이 가장 큰 등대)

맞는 말이지만 같은 영향력을 가진 등대가 여러개 있을 때 해답을 구하기 쉽지 않습니다.

 

그렇기에 영향력이 가장 큰 등대부터 찾는게 아니라 영향력이 가장 낮은 등대부터 찾는게

더욱 쉬울것 입니다.

 

영향력이 가장 낮은 등대는 가장 끝에 있는 등대입니다. 이 등대와 연결된 등대는 하나밖에 없기 때문에

불을 키는 것은 효율적이지 않습니다. 그럼 이 등대와 연결된 등대는 어떨까요?

가장 끝의 등대에 불을 키지 않았기 때문에 무조건 불을 켜주어야 할 것입니다.

 

이렇게 끝의 등대부터 탐색하여 무조건 켜야만 하는 등대들을 찾아주기만 하면

문제는 쉽게 해결됩니다.

 

정답 코드

#include <string>
#include <vector>

using namespace std;
vector<vector<int>> lights;
vector<bool> isLighting;
int answer = 0;

void DFS(int node, int parent)
{

    for (int& next : lights[node])
    {
        if (next != parent)
        {
            DFS(next, node);

            if (!isLighting[node] && !isLighting[next])
            {
                isLighting[node] = true;
                answer++;
            }
        }

    }
    
}

int solution(int n, vector<vector<int>> lighthouse) {
    lights.resize(n + 1);
    isLighting.resize(n + 1);
    for (auto& l : lighthouse)
    {
        lights[l[0]].push_back(l[1]);    
        lights[l[1]].push_back(l[0]);    
    }
    
    DFS(1, 0);
    return answer;
}