Programmers - 리틀 프렌즈 사천성

---

title: Programmers - 리틀 프렌즈 사천성
date: 2022-07-27
tags:

• Algorithm

---

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

문제 요약

사천성 게임에서 타일을 제거할 때, 경로에 아무것도 없어야 하며 경로를 90도로 한 번만 꺾을 수 있다.
모든 타일을 제거할 수 있을 때, 알파벳 순으로 가장 먼저인 순서로 문자열을 구성한다. 불가능하면 "IMPOSSIBLE"로 만든 후 return한다.

문제 풀이

타일을 제거하는 알고리즘을 구현하는 문제이다.
타일 확인시 같은 라인 혹은 더 낮은 라인에 있는 타일만 체크한다. 이렇게 하면 위쪽으로 매칭 가능한 타일이 있더라도 이미 체크가 끝난 후이다.
Right down, Down right, Down left, Left down 순으로 체크를 한다. 벽이나 잘못된 타일을 만나면 해당 방향의 탐색을 중지한다.
빈 공간일 경우, 90도를 꺾은 방향으로 동일하게 탐색한다.
처음에 'A', 'C' 두 가지를 제거 가능하며, 'A' 제거 후 'B'가 제거 가능하다고 하자. 이 경우 'A' - 'B' - 'C' 순서대로 제거해야 한다.
결국 하나의 타일을 제거한 후, 다시 제거 가능한 타일을 탐색해야 한다.
모든 타일이 제거될 때까지 반복하며, 타일이 남아있지만 제거할 수 없다면 "IMPOSSIBLE", 모든 타일을 제거했다면 제거한 순서대로 문자열을 구성한다.


처음에는 모든 타일을 검사하였다. 약 190ms의 시간이 걸렸으며, 이것은 효율성이 좋지 못하다.
n번째 단계에서 'C', 'G' 를 발견하였다고 가정하자. 그렇다면 'C'를 제거할 것이며, 다음 단계에서는 'G' 타일은 무조건 발견한다.
그렇기에 'G'보다 큰 타일에 대해서는 검사를 할 필요가 없다. 이 부분을 개선하여 약 31ms까지 시간을 줄였다.
여기서 다시 한 번 개선을 시도하였다. 이전의 프로그램은 현재 제거 대상 타일의 정보만 가지고 있으나, 한 번 찾은 타일을 다시 찾을 필요가 있을까?
그렇기에 priority_queue를 이용하였다. 타일을 찾을 때마다 priority_queue에 넣어주며, top에 위치한 타일보다 큰 타일은 무시한다.
또한, 우선 찾은 타일들은 장애물로 바꾸어 놓는다. 이 경우 찾은 타일과 함께 제거되는 pair 타일에 대한 탐색을 시도하지 않는다.
이 두 가지 개선 덕분에 약 18ms까지 시간을 줄일 수 있었다.
네 방향으로 제거 가능한 타일을 찾을 때, board에 대한 탐색 시간을 줄인다면 더욱 좋은 성능을 가져올 것이다.

프로그램 using Priority Queue

#include <string>
#include <vector>
#include <queue>
#include <utility>

using std :: vector ;
using std :: string ;
using std :: priority_queue ;
using std :: pair ;
using std :: make_pair ;

struct Node
{
    pair < int , int > pFirst ;
    pair < int , int > pSecond ;
    char cTile ;

    Node ( pair < int , int > pFirst , pair < int , int > pSecond , char cTile )
        : pFirst ( pFirst ) , pSecond ( pSecond ) , cTile ( cTile ) {}
} ;

struct comp
{
    bool operator () ( Node & a , Node & b )
    {
        if ( a.cTile > b.cTile )
            return true ;

        return false ;
    }
} ;

int iWidth ;
int iHeight ;

pair < int , int > getMatchingTile ( vector < string > & vpBoard , int iX , int iY , char cTile )
{
    for ( int j = iY + 1 ; j < iHeight ; ++j )                // Right down
    {
        char cTempTile = vpBoard [ iX ] [ j ] ;

        if ( '*' == cTempTile )
            break ;
        if ( '.' == cTempTile )
        {
            for ( int i = iX + 1 ; i < iWidth ; ++i )
            {
                cTempTile = vpBoard [ i ] [ j ] ;

                if ( '*' == cTempTile )
                    break ;
                if ( '.' == cTempTile )
                    continue ;
                else                                        // Find matching tile, RIGHT
                {
                    if ( cTempTile == cTile )
                        return make_pair ( i , j ) ;

                    break ;
                }
            }

            continue ;
        }
        else                                                // Find matching tile, RIGHT
        {
            if ( cTempTile == cTile )
                return make_pair ( iX , j ) ;

            break ;
        }
    }
    for ( int i = iX + 1 ; i < iWidth ; ++i )                // Down
    {
        char cTempTile = vpBoard [ i ] [ iY ] ;

        if ( '*' == cTempTile )
            break ;
        if ( '.' == cTempTile )
        {
            for ( int j = iY + 1 ; j < iHeight ; ++j )        // Down right
            {
                cTempTile = vpBoard [ i ] [ j ] ;

                if ( '*' == cTempTile )
                    break ;
                if ( '.' == cTempTile )
                    continue ;
                else                                        // Find matching tile, DOWN RIGHT
                {
                    if ( cTempTile == cTile )
                        return make_pair ( i , j ) ;

                    break ;
                }
            }
            for ( int j = iY - 1 ; j >= 0 ; --j )            // Down left
            {
                cTempTile = vpBoard [ i ] [ j ] ;

                if ( '*' == cTempTile )
                    break ;
                if ( '.' == cTempTile )
                    continue ;
                else                                        // Find matching tile, DOWN LEFT
                {
                    if ( cTempTile == cTile )
                        return make_pair ( i , j ) ;

                    break ;
                }
            }

            continue ;
        }
        else                                                // Find matching tile, DOWN
        {
            if ( cTempTile == cTile )
                return make_pair ( i , iY ) ;

            break ;
        }
    }
    for ( int j = iY - 1 ; j >= 0 ; --j )                    // Left down
    {
        char cTempTile = vpBoard [ iX ] [ j ] ;

        if ( '*' == cTempTile )
            break ;
        if ( '.' == cTempTile )
        {
            for ( int i = iX + 1 ; i < iWidth ; ++i )
            {
                cTempTile = vpBoard [ i ] [ j ] ;

                if ( '*' == cTempTile )
                    break ;
                if ( '.' == cTempTile )
                    continue ;
                else                                        // Find matching tile, RIGHT DOWN
                {
                    if ( cTempTile == cTile )
                        return make_pair ( i , j ) ;

                    break ;
                }
            }

            continue ;
        }
        else
            break ;
    }

    return make_pair ( -1 , 0 ) ;
}

string solution(int m, int n, vector<string> board )
{
    string answer = "";
    int iTileCount = 0 ;
    iWidth = m ;
    iHeight = n ;
    priority_queue < Node , vector < Node > , comp > pq ;
    char cTile = 'Z' + 1 ;



    for ( int i = 0 ; i < m ; ++i )
    {
        const char * cpString = board [ i ].data () ;

        for ( int j = 0 ; j < n ; ++j )
        {
            if ( ( '.' != * cpString ) && ( '*' != * cpString ) )
                ++ iTileCount ;

            ++ cpString ;
        }
    }

    iTileCount >>= 1 ;
    while ( 0 != iTileCount )
    {
        for ( int i = 0 ; i < m ; ++i )                // Find matching tile
        {
            for ( int j = 0 ; j < n ; ++j )
            {
                char cTempTile = board [ i ] [ j ] ;

                if ( ( '.' == cTempTile ) || ( '*' == cTempTile ) || ( cTile <= cTempTile ) )
                    continue ;

                pair < int , int > pMatchingTile = getMatchingTile ( board , i , j , cTempTile ) ;

                if ( -1 != pMatchingTile.first )
                {
                    pq.emplace ( make_pair ( i , j ) , pMatchingTile , cTempTile ) ;
                    board [ i ] [ j ] = '*' ;
                    board [ pMatchingTile.first ] [ pMatchingTile.second ] = '*' ;
                }
            }
        }

        if ( pq.empty () )
        {
            answer = "IMPOSSIBLE" ;

            break ;
        }

        Node tempNode = pq.top () ;                    // Erase matching tile
        pq.pop () ;

        -- iTileCount ;
        answer += tempNode.cTile ;
        board [ tempNode.pFirst.first ] [ tempNode.pFirst.second ] = '.' ;
        board [ tempNode.pSecond.first ] [ tempNode.pSecond.second ] = '.' ;

        if ( pq.empty () )
            cTile = 'Z' + 1 ;
        else
            cTile = pq.top ().cTile ;
    }


    return answer ;
}

프로그램 using Variable

#include <string>
#include <vector>
#include <utility>

using std :: vector ;
using std :: string ;
using std :: pair ;
using std :: make_pair ;

int iWidth ;
int iHeight ;

pair < int , int > getMatchingTile ( vector < string > & vpBoard , int iX , int iY , char cCurrentTile )
{
    for ( int j = iY + 1 ; j < iHeight ; ++j )                // Right down
    {
        char cTempTile = vpBoard [ iX ] [ j ] ;

        if ( '*' == cTempTile )
            break ;
        if ( '.' == cTempTile )
        {
            for ( int i = iX + 1 ; i < iWidth ; ++i )
            {
                cTempTile = vpBoard [ i ] [ j ] ;

                if ( '*' == cTempTile )
                    break ;
                if ( '.' == cTempTile )
                    continue ;
                else                                        // Find matching tile, RIGHT
                {
                    if ( cTempTile == cCurrentTile )
                        return make_pair ( i , j ) ;

                    break ;
                }
            }

            continue ;
        }
        else                                                // Find matching tile, RIGHT
        {
            if ( cTempTile == cCurrentTile )
                return make_pair ( iX , j ) ;

            break ;
        }
    }
    for ( int i = iX + 1 ; i < iWidth ; ++i )                // Down
    {
        char cTempTile = vpBoard [ i ] [ iY ] ;

        if ( '*' == cTempTile )
            break ;
        if ( '.' == cTempTile )
        {
            for ( int j = iY + 1 ; j < iHeight ; ++j )        // Down right
            {
                cTempTile = vpBoard [ i ] [ j ] ;

                if ( '*' == cTempTile )
                    break ;
                if ( '.' == cTempTile )
                    continue ;
                else                                        // Find matching tile, DOWN RIGHT
                {
                    if ( cTempTile == cCurrentTile )
                        return make_pair ( i , j ) ;

                    break ;
                }
            }
            for ( int j = iY - 1 ; j >= 0 ; --j )            // Down left
            {
                cTempTile = vpBoard [ i ] [ j ] ;

                if ( '*' == cTempTile )
                    break ;
                if ( '.' == cTempTile )
                    continue ;
                else                                        // Find matching tile, DOWN LEFT
                {
                    if ( cTempTile == cCurrentTile )
                        return make_pair ( i , j ) ;

                    break ;
                }
            }

            continue ;
        }
        else                                                // Find matching tile, DOWN
        {
            if ( cTempTile == cCurrentTile )
                return make_pair ( i , iY ) ;

            break ;
        }
    }
    for ( int j = iY - 1 ; j >= 0 ; --j )                    // Left down
    {
        char cTempTile = vpBoard [ iX ] [ j ] ;

        if ( '*' == cTempTile )
            break ;
        if ( '.' == cTempTile )
        {
            for ( int i = iX + 1 ; i < iWidth ; ++i )
            {
                cTempTile = vpBoard [ i ] [ j ] ;

                if ( '*' == cTempTile )
                    break ;
                if ( '.' == cTempTile )
                    continue ;
                else                                        // Find matching tile, RIGHT DOWN
                {
                    if ( cTempTile == cCurrentTile )
                        return make_pair ( i , j ) ;

                    break ;
                }
            }

            continue ;
        }
        else
            break ;
    }

    return make_pair ( -1 , 0 ) ;
}

string solution(int m, int n, vector<string> board )
{
    string answer = "";
    int iTileCount = 0 ;
    iWidth = m ;
    iHeight = n ;
    pair < int , int > pFirst = { 0 , 0 } ;
    pair < int , int > pSecond = { 0 , 0 } ;
    char cCurrentTile ;
    char cNextTile = 'Z' + 1 ;



    for ( int i = 0 ; i < m ; ++i )
    {
        const char * cpString = board [ i ].data () ;

        for ( int j = 0 ; j < n ; ++j )
        {
            if ( ( '.' != * cpString ) && ( '*' != * cpString ) )
                ++ iTileCount ;

            ++ cpString ;
        }
    }

    iTileCount >>= 1 ;
    while ( 0 != iTileCount )
    {
        cCurrentTile = cNextTile ;
        cNextTile = 'Z' + 1 ;

        for ( int i = 0 ; i < m ; ++i )            // Find matching tile
        {
            for ( int j = 0 ; j < n ; ++j )
            {
                char cTempTile = board [ i ] [ j ] ;

                if ( ( '.' == cTempTile ) || ( '*' == cTempTile ) || ( cCurrentTile < cTempTile ) )
                    continue ;

                pair < int , int > pMatchingTile = getMatchingTile ( board , i , j , cTempTile ) ;

                if ( -1 != pMatchingTile.first )
                {
                    if ( cTempTile < cCurrentTile )
                    {
                        pFirst.first = i ;
                        pFirst.second = j ;
                        pSecond = pMatchingTile ;
                        cCurrentTile = cTempTile ;
                    }
                    else if ( cTempTile < cNextTile )
                    {
                        cNextTile = cTempTile ;
                    }
                }
            }
        }

        if ( 'Z' + 1 == cCurrentTile )
        {
            answer = "IMPOSSIBLE" ;

            break ;
        }


        -- iTileCount ;
        answer += cCurrentTile ;
        board [ pFirst.first ] [ pFirst.second ] = '.' ;
        board [ pSecond.first ] [ pSecond.second ] = '.' ;
    }


    return answer ;
}