Programmers - 등대

---

title: Programmers - 등대
date: 2022-10-29
tags:

• Algorithm
• DP

---

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

문제 요약

Cycle이 없는 Graph가 주어진다.
각 Edge의 끝 Vertex중 하나는 불이 켜져있어야 할 때, 최소로 불을 킬 경우에 켜진 Vertex의 수를 return한다.

문제 풀이

최대 Vertex는 100K이며, Edge의 개수는 Vertex - 1 이다. Adjacent Matrix를 사용할 수 없는 문제이다.
처음에는 한 쪽에 불이 켜져있다면 다른 쪽은 무조건 꺼져있으면 되는 줄 알았으나, 예시에 나온것만 봐도 양쪽 모두 불이 켜져있을 수 있다.
한 쪽의 불이 꺼져있다면 다른 쪽은 무조건 켜져있어야 하나, 한 쪽이 켜져있을 경우 다른 쪽은 켜졌을 때와 꺼졌을 때 모두 확인하여야 한다는 것이다.
결국 모든 경우의 수를 점검해야 하지만 Brute Force로는 해결할 수 없다.
한 Edge를 기준으로 해당 Edge가 없다고 가정할 경우, Graph의 Subtree로 나뉘는 것을 알 수 있다.
결국 Root Node를 정하고 방향성을 정해주면 Subtree에서의 최소값을 찾는 문제로 바뀌며, 이는 DP 문제임을 알 수 있다.


우선 Adjacent List로 간선을 정리한 후, 각 Node를 기준으로 불이 켜졌을 때와 꺼졌을 때의 DP 값을 저장하는 DP vector를 생성한다.
Root Node는 무엇이 되어도 상관 없으므로 0번 Node를 Root로 취급하고, 이 Node의 불이 켜졌을 때와 꺼졌을 때의 최소값을 구해야 한다.
DFS 방식으로 비교하며, 현재 불의 상태와 DP 값이 존재하는지에 따라 처리가 다르다.
불이 꺼져있다면 다음 Node는 무조건 불이 켜져야 하며, 해당 DP값을 확인한다.
불이 켜져있다면 다음 Node는 모두 가능하기에 불이 켜졌을 때와 불이 꺼졌을 때의 DP값이 모두 존재해야 한다. 하나라도 없다면 DFS를 통해 다시 DP 값을 구한다.


이 문제의 Graph를 Tree로 취급할 수 있어야 해결 가능하다.
Vertex보다 Edge의 개수가 적기에 Cycle이 존재하지 않으며, 이 때문에 Tree로 취급할 수 있다.
사실 Graph로 인식하기 좋은 것을 Tree로 바꿀 수 있기에 이 문제는 Graph와 관련된 문제가 아니다.
그저 Subtree의 최적 값들을 어떻게 찾아낼 수 있는지, 이 때 DP를 떠올릴 수 있는지를 확인하는 문제이다.

프로그램

#include <vector>
#include <algorithm>

using std :: vector ;
using std :: min ;

int iGetLightSum ( vector < vector < int > > & vAdjacent , vector < vector < int > > & vDP , int iFormer , int iIndex , bool bLight )
{
    int iSize = vAdjacent [ iIndex ] .size () ;
    int iSum = bLight ? 1 : 0 ;



    for ( int i = 0 ; i < iSize ; ++i )
    {
        int iNext = vAdjacent [ iIndex ] [ i ] ;

        if ( iFormer != iNext )
        {
            if ( ( ! bLight ) && ( -1 != vDP [ iNext ] [ true ] ) )
            {
                iSum += vDP [ iNext ] [ true ] ;
            }
            else if ( ( bLight ) && ( -1 != vDP [ iNext ] [ true ] ) && ( -1 != vDP [ iNext ] [ false ] ) )
            {
                iSum += min ( vDP [ iNext ] [ true ] , vDP [ iNext ] [ false ] ) ;
            }
            else
            {
                if ( -1 == vDP [ iNext ] [ true ] )
                    vDP [ iNext ] [ true ] = iGetLightSum ( vAdjacent , vDP , iIndex , iNext , true ) ;
                if ( -1 == vDP [ iNext ] [ false ] )
                    vDP [ iNext ] [ false ] = iGetLightSum ( vAdjacent , vDP , iIndex , iNext , false ) ;

                if ( ! bLight )
                    iSum += vDP [ iNext ] [ true ] ;
                else
                    iSum += min ( vDP [ iNext ] [ true ] , vDP [ iNext ] [ false ] ) ;
            }
        }
    }

    return iSum ;
}

int solution ( int n , vector < vector < int > > lighthouse )
{
    vector < vector < int > > vAdjacent ( n ) ;
    vector < vector < int > > vDP ( n , vector < int > ( 2 , -1 ) ) ;    // [ DP with false, DP with true ]



    for ( int i = 0 ; i < n - 1 ; ++i )
    {
        int iNode1 = lighthouse [ i ] [ 0 ] - 1 ;
        int iNode2 = lighthouse [ i ] [ 1 ] - 1 ;

        vAdjacent [ iNode1 ].emplace_back ( iNode2 ) ;
        vAdjacent [ iNode2 ].emplace_back ( iNode1 ) ;
    }

    int iAnswer = iGetLightSum ( vAdjacent , vDP , -1 , 0 , true ) ;

    return min ( iAnswer , n - iAnswer ) ;
}

int main ()
{
    int i = solution ( 8, {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {5, 6}, {5, 7}, {5, 8}} ) ;
}