Programmers - 기둥과 보 설치

---

title: Programmers - 기둥과 보 설치
date: 2022-08-27
tags:

• Algorithm

---

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

문제 요약

기둥과 보는 조건에 맞아야 설치가 가능하다. 자세한 조건은 문제를 직접 보는 것이 이해하기 쉽다.
기둥과 보의 설치 및 삭제가 순서대로 주어질 때, 최종적으로 건설한 기둥과 보를 주어진 순서에 맞게 vector에 넣어 return한다.

문제 풀이

이 문제가 진짜 알고리즘 문제인 것 같다.
처음에 문제를 잘못 이해하고, 알고리즘 설계를 잘못하여 3일이라는 시간을 낭비하였다.


설치 가능 유무를 판단하는 bIsBuildingPossible 함수에서는 너무 복잡한 조건들을 설정하여 수정이 매우 어려웠다.
또한 기둥 설치시 보의 한쪽 끝 부분 위에 있거나 의 의미를 길게 이어진 보의 끝 부분이라고 판단하여 잘못된 비교가 이루어졌다.
이러한 부분을 오로지 문제의 설치 조건만 확인하도록 수정하였다.
설치가 가능한지만 판단하여 이외의 경우는 모두 불가능하다고 판단하도록 하였으며, 최소한의 조건을 이용하여 성능과 좋은 프로그램 모두를 챙겼다.

삭제 가능 유무를 판단하는 bIsBreakingPossible 함수에서는 bIsBuildingPossible 함수를 이용하지 않아 매우 복잡하고 과한 비교가 이루어졌다.
bIsBuildingPossible 함수를 이용하면 쉽게 해결할 수 있지만 이를 사용하지 않아 단일 함수에 100줄이 넘는 기괴한 프로그램을 작성하였다.
이 부분 또한 해당 프레임의 제거에 영향을 받는 직접적으로 연결된 프레임에 대해서만 bIsBuildingPossible 함수를 이용하여 확인하도록 바꾸었다.
현재 위치의 프레임 제거 없이 비교할 경우 현재 위치의 기둥과 보로 인하여 설치 가능하기에 삭제가 이루어지지 않는다.
그렇기에 현재 위치의 프레임을 먼저 제거한 후, 삭제가 불가능할 경우 다시 프레임을 설치하도록 프로그램을 구성하였다.


결과적으로 200줄이 넘으며 유지보수가 매우 어려운 난해한 프로그램이 약 120줄의 간결하고 유지보수가 쉬운 프로그램으로 바뀌었다.
최대 약 0.6ms의 적당히 괜찮은 성능을 확인할 수 있다.

프로그램

#include <vector>

using std :: vector ;

bool bIsBuildingPossible ( int iX , int iY , int iFrame , vector < vector < int > > & vFrame )
{
    int iSize = vFrame.size () ;



    if ( 1 == iFrame )            // Pillar
    {
        if ( ( 0 == iY ) || ( 1 == ( vFrame [ iX ] [ iY - 1 ] & 1 ) ) )        // Bottom or below pillar exist
            return true ;
        if ( 2 == ( vFrame [ iX ] [ iY ] & 2 ) )                            // Pillar at left of beam
            return true ;
        if ( ( 0 != iX ) && ( 2 == ( vFrame [ iX - 1 ] [ iY ] & 2 ) ) )        // Pillar at right of beam
            return true ;
    }
    else if ( 2 == iFrame )        // Beam
    {
        if ( 0 == iY )                                        // Bottom
            return true ;
        if ( 1 == ( vFrame [ iX ] [ iY - 1 ] & 1 ) )        // left below pillar exist
            return true ;
        if ( 1 == ( vFrame [ iX + 1 ] [ iY - 1 ] & 1 ) )    // Right below pillar exist
            return true ;
        if ( ( 0 != iX ) && ( iX + 2 < iSize ) && ( 2 == ( vFrame [ iX - 1 ] [ iY ] & 2 ) ) && ( 2 == ( vFrame [ iX + 1 ] [ iY ] & 2 ) ) )    // both side beam exist
            return true ;
    }


    return false ;
}

bool bIsBreakingPossible ( int iX , int iY , int iFrame , vector < vector < int > > & vFrame )
{
    int iSize = vFrame.size () ;



    vFrame [ iX ] [ iY ] &= ~ iFrame ;

    if ( 1 == iFrame )
    {
        if ( ( iY + 2 < iSize ) && ( 1 == ( vFrame [ iX ] [ iY + 1 ] & 1 ) ) && ! bIsBuildingPossible ( iX , iY + 1 , 1 , vFrame ) )        // Upper pillar exist, can't place
            return false ;
        if ( ( 0 != iX ) && ( 2 == ( vFrame [ iX - 1 ] [ iY + 1 ] & 2 ) ) && ! bIsBuildingPossible ( iX - 1 , iY + 1 , 2 , vFrame ) )        // Left upper beam exist, can't place
            return false ;
        if ( ( iFrame + 1 < iSize ) && ( 2 == ( vFrame [ iX ] [ iY + 1 ] & 2 ) ) && ! bIsBuildingPossible ( iX , iY + 1 , 2 , vFrame ) )    // Right upper beam exist, can't place
            return false ;
    }
    else if ( 2 == iFrame )
    {
        if ( ( iY + 1 < iSize ) && ( 1 == ( vFrame [ iX ] [ iY ] & 1 ) ) && ! bIsBuildingPossible ( iX , iY , 1 , vFrame ) )            // Left upper pillar exist, can't place
            return false ;
        if ( ( iY + 1 < iSize ) && ( 1 == ( vFrame [ iX + 1 ] [ iY ] & 1 ) ) && ! bIsBuildingPossible ( iX + 1 , iY , 1 , vFrame ) )    // Right upper pillar exist, can't place
            return false ;
        if ( ( 0 != iX ) && ( 2 == ( vFrame [ iX - 1 ] [ iY ] & 2 ) ) && ! bIsBuildingPossible ( iX - 1 , iY , 2 , vFrame ) )            // Left beam exist, can't place
            return false ;
        if ( ( iX + 2 < iSize ) && ( 2 == ( vFrame [ iX + 1 ] [ iY ] & 2 ) ) && ! bIsBuildingPossible ( iX + 1 , iY , 2 , vFrame ) )    // Right beam exist, can't place
            return false ;
    }


    return true ;
}

vector < vector < int > > solution ( int n , vector < vector < int > > build_frame )
{
    vector < vector < int > > answer ;
    vector < vector < int > > vFrame ( n + 1 , vector < int > ( n + 1 , 0 ) ) ;        // 0 Nothing, 1 Pillar, 2 Beam
    int iBuildSize = build_frame.size () ;



    for ( int i = 0 ; i < iBuildSize ; ++i )
    {
        int iX = build_frame [ i ] [ 0 ] ;
        int iY = build_frame [ i ] [ 1 ] ;
        int iFrame = build_frame [ i ] [ 2 ] + 1 ;
        bool bBuild = 1 == build_frame [ i ] [ 3 ] ;


        if ( bBuild && bIsBuildingPossible ( iX , iY , iFrame , vFrame ) )
        {
            vFrame [ iX ] [ iY ] |= iFrame ;
        }
        else if ( ! bBuild )
        {
            if ( ! bIsBreakingPossible ( iX , iY , iFrame , vFrame ) )    // If can break, already broke at bIsBreakingPossible
                vFrame [ iX ] [ iY ] |= iFrame ;                        // If cannot, rebuild frame
        }
    }

    for ( int i = 0 ; i < n + 1 ; ++i )
    {
        for ( int j = 0 ; j < n + 1 ; ++j )
        {
            if ( 0 != vFrame [ i ] [ j ] )
            {
                vector < int > vTemp ( 3 ) ;

                vTemp [ 0 ] = i ;
                vTemp [ 1 ] = j ;

                if ( 1 == ( vFrame [ i ] [ j ] & 1 ) )
                {
                    vTemp [ 2 ] = 0 ;
                    answer.emplace_back ( vTemp ) ;
                }
                if ( 2 == ( vFrame [ i ] [ j ] & 2 ) )
                {
                    vTemp [ 2 ] = 1 ;
                    answer.emplace_back ( vTemp ) ;
                }
            }
        }
    }


    return answer ;
}