프로그래머스 문제 - 등대

프로그래머스 등대 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

바다에 1부터 n까지 서로 다른 번호가 매겨진 등대가 존재합니다.
등대와 등대 사이를 오가는 뱃길이 존재하며 어느 등대에서 출발해도 다른 모든 등대까지 이동이 가능합니다.
전력을 아끼기 위하여 한 뱃길의 양쪽 끝 등대 중 적어도 한 개의 등대가 켜져 있도록 해야 합니다.
켜 두어야 하는 등대 개수의 최솟값을 출력해야 합니다.

문제 풀이

간선으로 이어진 등대들을 조건에 맞춰 켜야 합니다.

문제를 보다보면 한 등대를 중심으로 트리를 만들어보면 최소한의 등대를 키기 위해서 자식 노드가 없는 등대들은 무조건 등대를 키지 않고 부모 등대가 불이 켜져야 한다는 것을 알 수 있습니다.
그러니 dfs를 사용하여 아래서부터 검색을 시작해 바로 1칸 내의 하위 노드들 중 불을 킨 노드가 한곳이라도 존재하지 않는다면 현재 등대를 켜주면 됩니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

vector<int> lighthouses[100001];
int answer; 

bool solve(int cur, int parent)
{
    int isUsingLight = false;
    
    //하위 노드들 검색
    for(int n : lighthouses[cur])
    {
        if(n != parent)
        {
            //만약 근처의 하위 노드들이 불을 키지 않았을 경우
            if(!solve(n, cur))
            {
                //현재 등불은 불이 켜져야 함
                isUsingLight = true;
            }
        }
    }
    
    //불이 켜졌을 때 갯수를 더해줌
    if(isUsingLight)
    {
        answer++;
    }
    
    return isUsingLight;
}

int solution(int n, vector<vector<int>> lighthouse) {
    answer = 0;
    
    //간선 등록
    for(vector<int> v : lighthouse)
    {
        lighthouses[v[0]].push_back(v[1]);
        lighthouses[v[1]].push_back(v[0]);
    }
    solve(1, 1);
    
    return answer;
}

출저

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