Programmers - 전력망을 둘로 나누기

---

title: Programmers - 전력망을 둘로 나누기
date: 2022-06-26
tags:

• Algorithm
• BFS

---

https://programmers.co.kr/learn/courses/30/lessons/86971

문제 요약

Tree 구조로 이루어진 전력망이 존재한다. 전선을 하나 끊어 두 전력망으로 나누는데, 두 전력망의 개수가 가장 비슷하도록 나누었을 때의 개수 차이를 return한다.

문제 풀이

송전탑의 개수는 100개가 최대이다. Tree 구조이기에 전선의 개수는 99개가 최대이며, 최악의 경우 전선 99개 * 송전탑 전체 탐색 100회 = 9900회의 탐색이 이루어진다.
횟수가 별로 많지 않으므로 주어진 데이터를 그대로 이용한다. 만약 n의 최대치가 100이 아닌 10k, 100k 등이 된다면 데이터의 가공이 필요할 것으로 보인다.
Root 노드를 기준으로 child와 parent를 가리키도록 하며 각 level, 해당 노드 기준으로 좌,우에 몇개의 노드가 있는지 저장하는 방식이 괜찮을 것 같다.
n-1번만큼 loop를 돌며 하나의 전선을 끊고, 한 쪽에서만 BFS를 시행한다. 한 쪽에서 i개의 송전탑이 존재하면 반대쪽에서 n - i개의 송전탑이 존재할 것이다.

보통 Programmers의 테스트 결과는 0.01~0.1ms를 기록하였는데, 이번에는 평균적으로 0.8-1ms가 되는 것 같다. 시간이 충분하기에 데이터를 가공하지 않고 무식하게 탐색하여 성능이 좋지 않았다.

추가적으로, 정답 프로그램 중 잘 모르는 C++ 문법이 존재하였다.

function<void(int, int)> dfs = [&](int cur, int prev)  -> void {
        siz[cur] = 1;
        for(int nxt : graph[cur]) {
            if(nxt == prev) continue;
            dfs(nxt, cur);
            siz[cur] += siz[nxt];
        }
    };
    dfs(1, -1);

이는 Lambda 함수이다. Lambda 함수란 익명의 함수를 일회성으로 사용하기 위한 목적으로 사용한다고 볼 수 있다.

[ Capture ] ( Parameter Head ) { Body } ( Parameter Use ) ;

Capture - 파라미터를 사용할 때 값을 복사하여 사용할 것인지, 이를 참조자로 사용할 것인지 명시하는 부분이다. '='의 경우 복사, '&'의 경우 참조자이다.
[& , a] , [= , &b] 와 같이 혼용하여 사용할 수 있다. 전자의 경우 a는 복사, 이외의 것은 참조로 사용한다. 후자의 경우 b는 참조, 이외의 것은 복사로 사용한다.
Parameter Head - Prototype과 같이 이후 사용하게 될 파라미터의 정보를 명시한다.
Body - 함수의 동작 부분
Parameter Use - 함수 호출시 파라미터로 넘겨주는 것과 동일하게 사용한다.

대표적으로 std :: sort 함수는 ascending order로 정렬이 되지만, descending order 혹은 다른 조건으로 정렬하고 싶을 경우 함수를 선언하여야 한다.
정렬에만 사용하기 위하여 함수를 선언하는 것은 아쉬우며, 이를 위해 Lambda 함수를 아래처럼 사용한다.

std :: sort ( vWire.begin () , vWire.end () , [] ( int a , int b ) { return a > b ; } ) ;

다시 본론으로 돌아와서, 처음 본 lambda 함수를 function 변수에 대입하여 사용하는 것을 확인하였다.
규모가 큰 프로젝트에서 A 함수를 Big 함수 내에서만 사용할 경우, 동일하게 변수에 대입하여 사용하는 것을 고려할지도 모른다.
다만, A 함수를 Big 함수 내부에서 선언하여 사용하는 것이 과연 clean한 좋은 코드인지는 고민해봐야 할 문제이다.

프로그램

#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>

using std :: vector ;
using std :: queue ;

int solution ( int n , vector < vector < int > > wires )
{
    int answer = 100 ;
    vector < int > * vpWire = wires.data () ;
    queue < int > qBFS ;
    vector < bool > vVisit ;                // Specialized version of vector
    vVisit.resize ( n ) ;
    int iCnt = 0 ;
    int iIndex = 0 ;



    for ( int i = 0 ; i < n - 1 ; ++i )        // n tower, n-1 wires
    {
        std :: fill ( vVisit.begin () , vVisit.end () , false ) ;
        iCnt = 1 ;
        iIndex = 0 ;
        vVisit [ 0 ] = true ;
        qBFS.emplace ( 0 ) ;

        while ( ! qBFS.empty () )
        {
            iIndex = qBFS.front () ;
            qBFS.pop () ;

            for ( int j = 0 ; j < n - 1 ; ++j )
            {
                if ( i == j )            // Cut this wire
                    continue ;

                int iNode1 = vpWire [ j ] [ 0 ] - 1 ;
                int iNode2 = vpWire [ j ] [ 1 ] - 1 ;

                if ( iNode2 == iIndex )        // If iNode2 is iIndex, then swap with 1
                {
                    iNode1 += iNode2 ;
                    iNode2 = iNode1 - iNode2 ;
                    iNode1 -= iNode2 ;
                }

                if ( ( iNode1 == iIndex ) && ( ! vVisit [ iNode2 ] ) )        // Find new node to check
                {
                    vVisit [ iNode2 ] = true ;
                    qBFS.emplace ( iNode2 ) ;

                    ++ iCnt ;
                }
            }
        }

        answer = std :: min ( answer , abs ( n - 2 * iCnt ) ) ;        // iCnt , n - iCnt. Latter - former = n - 2 * iCnt
    }


    return answer ;
}