등대

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

구현 아이디어 8분 구현 32분

풀이(실패)

틀린 풀이다. 일단 1번째 틀린 풀이를 기록한다.

• 임의의 등대부터 출발하여 출발 등대가 켜져있을 때, 꺼져있을 때 중 적은 값을 answer에 대입하려 했다.
  반례: 8, [[1, 2], [1, 3], [1, 4], [1, 5], [5, 6], [5, 7], [5, 8]]
기댓값: 2, 출력값: 4

#include <string>
#include <vector>

using namespace std;

// 임의의 노드에서 출발.
// 출발 노드가 켜져있을 때, 꺼져있을 때로 구분, 비교.

vector<int> tree[100001];
int check[100001];
int sum = 0;

void DFS(int LighthouseIndex, bool bTurnOn)
{
    if(bTurnOn) ++sum;
    if(tree[LighthouseIndex].size() == 1 && check[tree[LighthouseIndex][0]])
    {
        // 연결된 등대가 1개고, 그 등대는 이미 체킹된(방문된) 경우.
        return;
    }
    else
    {
        for(int i = 0; i < tree[LighthouseIndex].size(); ++i)
        {
            int child_index = tree[LighthouseIndex][i];
            if(check[child_index] == 0)
            {
                check[child_index] = 1;
                DFS(child_index, !bTurnOn);
            }
        }
    }
}

int solution(int n, vector<vector<int>> lighthouse) {
    int answer = 0;
    
    for(int i = 0; i < n - 1; ++i)
    {
        int lighthouse1 = lighthouse[i][0];
        int lighthouse2 = lighthouse[i][1];
        //printf("%d %d\n", lighthouse1, lighthouse2);
        tree[lighthouse1].push_back(lighthouse2);
        tree[lighthouse2].push_back(lighthouse1);
    }
    
    check[1] = 1;
    
    bool bTurnOn = true;
    DFS(1, !bTurnOn);
    int mini1 = sum;
    
    for(int i = 2; i <= n; ++i)
        check[i] = 0;
    
    sum = 0;
    DFS(1, bTurnOn);
    int mini2 = sum;
    
    answer = min(mini1, mini2);
    
    return answer;
}

---

풀이

백준 2533번: 사회망 서비스(SNS) 문제와 같다.

• 부모가 꺼져있다면 자식은 켜져있어야 한다. 켜져있는 경우를 더한다.
• 부모가 켜져있다면 자식은 켜져있거나 꺼져있는 경우 중 적은 값을 더한다.

#include <string>
#include <vector>

using namespace std;

vector<int> maps[100001];
int check[100001];
int dp[100001][2];  // 0이 꺼져있는 것, 1이 켜져있는 것.

void DFS(int lighthouseIndex)
{
    check[lighthouseIndex] = 1;
    dp[lighthouseIndex][1] = 1;
    
    // 꺼져있다면 자식은 켜져있어야 함.
    // 켜져있다면 자식은 켜져있는 것과 꺼져있는 것 중 적은 값을 택함.
    for(int i = 0; i < maps[lighthouseIndex].size(); ++i)
    {
        int childLighthouse = maps[lighthouseIndex][i];
        if(check[childLighthouse]) continue;
        DFS(childLighthouse);
        dp[lighthouseIndex][0] += dp[childLighthouse][1];
        dp[lighthouseIndex][1] += (min(dp[childLighthouse][0], dp[childLighthouse][1]));
    }
}

int solution(int n, vector<vector<int>> lighthouse) {
    int answer = 0;
    
    for(int i = 0; i < n - 1; ++i)
    {
        int lighthouse1 = lighthouse[i][0];
        int lighthouse2 = lighthouse[i][1];
        
        maps[lighthouse1].push_back(lighthouse2);
        maps[lighthouse2].push_back(lighthouse1);
    }
    
    DFS(1);
    
    return answer = min(dp[1][0], dp[1][1]);
}

---

풀이(2023년 11월 29일)

#include <string>
#include <vector>

using namespace std;

// 사회망 서비스 문제와 같음.
int Dp[100001][2];  // 0은 꺼짐, 1은 켜짐.
vector<int> Maps[100001];
int Check[100001];

void DFS(int CurLightHouse)
{
    Check[CurLightHouse] = 1;
    Dp[CurLightHouse][1] = 1;
    
    for(int i = 0; i < Maps[CurLightHouse].size(); ++i)
    {
        int CheckLightHouse = Maps[CurLightHouse][i];
        if(Check[CheckLightHouse] == 1) continue;
        DFS(CheckLightHouse);
        Dp[CurLightHouse][0] += Dp[CheckLightHouse][1];
        Dp[CurLightHouse][1] += min(Dp[CheckLightHouse][0], Dp[CheckLightHouse][1]);
    }
}

int solution(int n, vector<vector<int>> lighthouse) {
    int answer = 0;
    
    for(int i = 0; i < lighthouse.size(); ++i)
    {
        int LightHouse1 = lighthouse[i][0];
        int LightHouse2 = lighthouse[i][1];
        Maps[LightHouse1].push_back(LightHouse2);
        Maps[LightHouse2].push_back(LightHouse1);
    }
    
    DFS(1);
    answer = min(Dp[1][0], Dp[1][1]);   // 켠 것, 끈 것 중에 적은 값.
    
    return answer;
}

---

유사 문제

https://www.acmicpc.net/problem/2533